17. Subsets

Given a set of distinct integers, return all possible subsets.

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets

根据第一条
ex:
S = [1, 2, 3]

1:
1
12
13
123

2:
2
23

3:
3

想法：
List<List<Integer>> res  = new List<List<Integer>()
for(int i = 0; i<S.size; i++) {
     List<Integer> prev = new ArrayList<>();
     prev.add(i);
     helper(
}

helper(List<Integer> prev, i, n, res) {
    if(i == n) {
        return;
    } else {
       
       for(int i = 0; i<S.size; i++) {
          List<Integer> cur = new ArrayList<>(prev);
          cur.add(i);
          res.add(cur);
          helper(cur, i+1, n, res)
       }
    }
}


Code（WA）

input：[1,2]

output：
[[],[1],[1,2],[2],[2,2]]


 

  public List<List<Integer>> subsets(int[] nums) {
        // write your code here
        List<List<Integer>> rst = new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> prev = new ArrayList<>();
        rst.add(prev);
       
        helper(prev, 0, nums, rst);
        return rst;
    }
   
    private void helper(List<Integer> prev, int i, int[] nums, List<List<Integer>> rst) {
        if(i == nums.length) {
            return;
        } else {
            for(int k = i; k < nums.length; k++) {
                List<Integer> cur = new LinkedList<>(prev);
                cur.add(nums[k]);
                rst.add(cur);
                helper(cur, i+1, nums, rst);
               
            }
        }
造成这个问题的原因是没有回溯
当找到【1，2】开头的结果后 没有remove 2
导致要找【1，3】开头的结果就会变成找【1，2，3】开头的结果   


Answer
public List<List<Integer>> subsets(int[] nums) {
        // write your code here
        List<List<Integer>> rst = new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> prev = new ArrayList<>();
        helper(prev, 0, nums, rst);
        return rst;
    }
   
    private void helper(List<Integer> subset, int start, int[] nums, List<List<Integer>> rst) {
        rst.add(new ArrayList<Integer>(subset));
        for(int i = start; i < nums.length; i++) {
            List<Integer> cur = new LinkedList<>(subset);
            cur.add(nums[i]);
            helper(cur, i+1, nums, rst);
           

// [1,2] -> [1]  回溯

            cur.remove(cur.size() - 1);
        }
    }