Subsets

Given a set of distinct integers,nums, return all possible subsets (the power set).

Note:The solution set must not contain duplicate subsets.

Example:

Input:
 nums = [1,2,3]

Output:

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

Analysis

Backtracking

典型的backtracking问题，可以用比较通用的模板来解决。

Iterative

https://leetcode.com/problems/subsets/discuss/122645/3ms-easiest-solution-no-backtracking-no-bit-manipulation-no-dfs-no-bullshit

While iterating through all numbers, for each new number, we can either pick it or not pick it

1, if pick, just add current number to every existing subset.

2, if not pick, just leave all existing subsets as they are.

We just combine both into our result.

For example, {1,2,3} intially we have an emtpy set as result [ [ ] ] Considering 1, if not use it, still [ ], if use 1, add it to [ ], so we have [1] now Combine them, now we have [ [ ], [1] ] as all possible subset

Next considering 2, if not use it, we still have [ [ ], [1] ], if use 2, just add 2 to each previous subset, we have [2], [1,2] Combine them, now we have [ [ ], [1], [2], [1,2] ]

Next considering 3, if not use it, we still have [ [ ], [1], [2], [1,2] ], if use 3, just add 3 to each previous subset, we have [ [3], [1,3], [2,3], [1,2,3] ] Combine them, now we have [ [ ], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3] ]

Bit Manipulation

https://leetcode.com/problems/subsets/discuss/122645/3ms-easiest-solution-no-backtracking-no-bit-manipulation-no-dfs-no-bullshit

Solution

Backtracking

class Solution {
    public List<List<Integer>> subsets(int[] ns) {
        List<List<Integer>> acc = new ArrayList<>();

        recur(acc, ns, new ArrayDeque<>(), 0);
        return acc;
    }

    private void recur(List<List<Integer>> acc, int [] ns, Deque<Integer> path, int start){
        if(ns.length == start){
            acc.add(new ArrayList<>(path));
            return;
        }

        // take ns[start]
        path.push(ns[start]);
        recur(acc, ns, path, start + 1);

        // dont take ns[start]
        path.pop();
        recur(acc, ns, path, start + 1);
    }
}

Another Backtracking

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);
    }
}

Iteration

public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for(int n : nums){
            int size = result.size();
            for(int i=0; i<size; i++){
                List<Integer> subset = new ArrayList<>(result.get(i));
                subset.add(n);
                result.add(subset);
            }
        }
        return result;
    }

Bit Manipulation

public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for(int n : nums){
            int size = result.size();
            for(int i=0; i<size; i++){
                List<Integer> subset = new ArrayList<>(result.get(i));
                subset.add(n);
                result.add(subset);
            }
        }
        return result;
    }

Reference

https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning\