78. 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],
  []
]

---
Intuition
Generate all combinations, save combination at each stage
---
Related problems
90-subsets-ii
46-permutations
47-permutations-ii
39-combination-sum
40-combination-sum-ii
---

	class Solution {
	public List<List<Integer>> subsets(int[] nums) {
	List<List<Integer>> ans = new ArrayList<List<Integer>>();
	ans.add(new ArrayList<Integer>());

	for (int n: nums) {
	int existing = ans.size();
	for (int i = 0; i < existing; i++) {
	List<Integer> prefix = new ArrayList<Integer>(ans.get(i));
	prefix.add(n);
	ans.add(prefix);
	}
	}
	return ans;
	}
	}

	class Solution {
	public List<List<Integer>> subsets(int[] nums) {
	List<List<Integer>> ans = new ArrayList<List<Integer>>();
	if (nums == null \|\| nums.length == 0) {
	return ans;
	}
	List<Integer> curr = new ArrayList<Integer>();

	dfs(nums, 0, curr, ans);
	return ans;
	}

	private void dfs(int[] nums, int i, List<Integer> curr, List<List<Integer>> ans) {
	if (i == nums.length) {
	ans.add(new ArrayList<Integer>(curr));
	return;
	}

	// include current element
	curr.add(nums[i]);
	dfs(nums, i + 1, curr, ans);
	curr.remove(curr.size() - 1);

	// skip current element
	dfs(nums, i + 1, curr, ans);
	}
	}

SWE Interview preparation