package algorithm;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

/**

* @ClassName Week5

* @Description TODO

* @Author Administrator

* @Date 2021/4/24 14:24

* @Version 1.0

**/

public class Week5 {

/**

* A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partioning)

*

* This structure might apply to many other backtracking questions, but here I am just going to demonstrate Subsets, Permutations, and Combination Sum.

*

* https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)

*

* *****************************************************************************************************************

*

* Subsets : https://leetcode.com/problems/subsets/

*/

public List<List<Integer>> subsets(int[] nums) {

List<List<Integer>> list = new ArrayList<>();

Arrays.sort(nums);

backtrack(list, new ArrayList<>(), nums, 0);

return list;

}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {

list.add(new ArrayList<>(tempList));

for (int i = start; i < nums.length; i++) {

tempList.add(nums[i]);

backtrack(list, tempList, nums, i + 1);

tempList.remove(tempList.size() - 1);

}

}

public static void main(String[] args) {

}

}