Subsets

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

Note:

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

For example,
If S = [1,2,3], a solution is:

[

  [3],

  [1],

  [2],

  [1,2,3],

  [1,3],

  [2,3],

  [1,2],

  []

]

就是一个DFS的过程，需要一个额外的index变量。注意这道题我们需要先sort下数组，这样才能保证升序。

public class Solution {
    //Time: O(n^n)
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        Arrays.sort(S);
        subsetHelp(res, tmp, S, 0);
        return res;
    }
    
    private void subsetHelp(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp, 
                            int[] S, int index) {
        res.add(new ArrayList<Integer>(tmp));
        
        for (int i = index; i < S.length; i++) {
            tmp.add(S[i]);
            subsetHelp(res, tmp, S, i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }
}

Given a collection of integers that might contain duplicates, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.
一样DFS，但是对于相邻两个元素相同的情况下，必须避免重复case。

public class Solution {
    //Time: O(n^n)
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        Arrays.sort(num);
        subsetsHelp(res, tmp, num, 0);
        return res;
    }
    
    private void subsetsHelp(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp,
                             int[] num, int index) {
        res.add(new ArrayList<Integer>(tmp));
        
        for (int i = index; i < num.length; i++) {
            if (i != index && num[i] == num[i - 1]) {
                continue;
            }
            
            tmp.add(num[i]);
            subsetsHelp(res, tmp, num, i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }
}