Subsets

★★☆☆☆

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

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

// recursive dfs solution
// push order: [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    ans.add(new ArrayList<Integer>());
    Arrays.sort(nums);
    return dfs(nums, 0, new ArrayList<Integer>(), ans);
}
public List<List<Integer>> dfs(int[] nums, int idx, List<Integer> subset, List<List<Integer>> ans) {
    if (idx == nums.length) return ans;
    for (int i = idx; i < nums.length; ++i) {
        subset.add(nums[i]);
        ans.add(new ArrayList<Integer>(subset));
        ans = dfs(nums, i+1, subset, ans);
        subset.remove(subset.size()-1);
    }
    return ans;
}


// iterative observation solution
// push order: []/ [1]/ [2], [1, 2]/ [3], [1, 3], [2, 3], [1, 2, 3]
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    ans.add(new ArrayList<Integer>());
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; ++i) {
        int prevSize = ans.size();
        for (int j = 0; j < prevSize; ++j) {
            List<Integer> tmp = new ArrayList<Integer>(ans.get(j));
            tmp.add(nums[i]);
            ans.add(tmp);
        }
    }
    return ans;
}

// bitwise iterative solution: https://goo.gl/yuW4wK