Subsets I

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

Notice

• Elements in a subset must be in_non-descending_order.

• The solution set must not contain duplicate subsets.

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

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution: Deep first search(Brute Force)

public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if (nums == null || nums.length == 0) {
        return res;
    }
    Arrays.sort(nums);

    ArrayList<Integer> items = new ArrayList<Integer>();
    for(int i = 0; i <= nums.length; i++) {
        dfs(nums, res, items, 0, i);
    }

    return res;
}

public void dfs(int[] nums, 
                ArrayList<ArrayList<Integer>> res, 
                ArrayList<Integer> items,
                int index,
                int len) {
    if(items.size() == len) {
        res.add(new ArrayList<>(items));
        return ;
    }

    for(int i = index; i < nums.length; i++) {
        items.add(nums[i]);
        dfs(nums, res, items, i + 1, len);
        items.remove(items.size() - 1);
    }
}

Subsets II

what if have duplicate number?

Solution: Skip the duplicate numbers.

public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if (nums == null || nums.length == 0) {
        return res;
    }
    Arrays.sort(nums);

    ArrayList<Integer> items = new ArrayList<Integer>();
    for(int i = 0; i <= nums.length; i++) {
        dfs(nums, res, items, 0, i);
    }

    return res;
}

public void dfs(int[] nums, 
                ArrayList<ArrayList<Integer>> res, 
                ArrayList<Integer> items,
                int index,
                int len) {
    if(items.size() == len) {
        res.add(new ArrayList<>(items));
        return ;
    }

    for(int i = index; i < nums.length; i++) {
        if(i > index && nums[i] == nums[i - 1])
            continue;
        items.add(nums[i]);
        dfs(nums, res, items, i + 1, len);
        items.remove(items.size() - 1);
    }
}