Subsets I & II, Java Solution with Detailed Explanation and Comments (Recursion & Iteration)
Reference: Subsets I & Subsets II EPI 15.5\nDifficulty: Medium (I think Subsets II should be hard)\n\n\n\n## Problem\n\n> Given a set of distinct integers, nums
Reference: [Subsets I](https://leetcode.com/problems/subsets/) & [Subsets II](https://leetcode.com/problems/subsets-ii/) <span class="gray">EPI 15.5</span>\nDifficulty: <span class="orange">Medium</span> (I think Subsets II should be hard)\n\n\n\n## Problem\n\n> Given a set of `distinct` integers, `nums`, return all possible subsets (the power set).\n\n**Note:** The solution set must not contain duplicate subsets.\n\n**Example:** \n\n```java\nInput: nums = [1,2,3]\nOutput: [\n  [3],\n  [1],\n  [2],\n  [1,2,3],\n  [1,3],\n  [2,3],\n  [1,2],\n  []\n]\n```\n\n**Follow up:** Check out the [Subsets II](#subsets_ii) section below.\n\n\n## Analysis\n\nThe power set of a set `S` is the set of all subsets of `S`, including both the empty set `emptyset` and `S` itself. The power set of `{1, 2, 3}` is graphically illustrated as follows.\n\n![](https://bloggg-1254259681.cos.na-siliconvalley.myqcloud.com/mgtg8.jpg)\n\n\n### Backtracking\n\nThe idea is that we loop over the number list. For each number, we have two choices: pick it, or not. For example, in `[1, 2, 3]`, we pick `1` and then do the same thing for the subproblem `[2, 3]`; and we don\'t pick `1` and then do the same thing for the subproblem `[2, 3]`.\n\nThe size of subproblems is decreasing. When picking `2`, the subproblem becomes `[3]` instead of `[1, 3]`.\n\nConsider the following questions:\n\n- What is the base case?\n- When do we add the list to the result?\n\nHere is an illustration of recursive process on `[1, 2, 3]`.\n\n![](https://bloggg-1254259681.cos.na-siliconvalley.myqcloud.com/gfdd3.jpg)\n\n\n**Note:** Remember to add empty set manually.\n\n\n```java\npublic List<List<Integer>> subsets(int[] nums) {\n  List<List<Integer>> result = new ArrayList<>();\n  List<Integer> numList = new ArrayList<>();\n  \n  result.add(new ArrayList<>()); // empty set\n  subsets(0, nums, numList, result);\n  return result;\n}\n\nprivate void subsets(int offset, int[] nums, List<Integer> numList, List<List<Integer>> result) {\n  if (offset >= nums.length) {\n    return;\n  }\n  int val = nums[offset];\n  // pick\n  numList.add(val);\n  subsets(offset + 1, nums, numList, result);\n  // add to result\n  result.add(new ArrayList<>(numList));\n  // not pick\n  numList.remove(numList.size() - 1);\n  subsets(offset + 1, nums, numList, result);\n}\n```\n\n**Time:** `O(N * 2^N)` since the recurrence is `T(N) = 2T(N - 1)` and we also spend at most `O(N)` time within a call.\n**Space:** `O(N * 2^N)` since there are `2^N` subsets. If we only print the result, we just need `O(N)` space.\n\n\n### Iteration\n\nThe idea is simple. We go through the elements in the `nums` list. For each element, we loop over the current `result` list we have constructed so far. For each list in the `result`, we make a copy of this list and append the current element to it (it means picking the element). It is based on the same idea in backtracking (in each step you have choices: `pick` or `not pick`).\n\nThe result list initially contains an empty list `[]`. We loop over each element of `nums`, e.g. `[1, 2, 3]`.\n\n- After the first round, we have `[[], [1]]`.\n- After the second round, we have `[[], [1], [2], [1,2]]`.\n- After the third round, we have `[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]`.\n\nFirst, let\'s go over an incorrect version. There are two errors:\n\n1. We add a new element to `L`, but it changes the existed `L`. Thus, we should make a new copy of it.\n2. While looping over `result`, we are modifying its size. In Java, the compiler would yell.\n\n**Incorrect version:**\n\n```java\npublic List<List<Integer>> subsets(int[] nums) {\n  List<List<Integer>> result = new ArrayList<>();\n  result.add(new ArrayList<>());  // empty set\n  for (int i = 0; i < nums.length; ++i) {\n    for (List<Integer> L : result) {\n      L.add(nums[i]);\n      result.add(L);\n    }\n  }\n  return result;\n}\n```\n\n**Correct version:**\n\n```java\npublic List<List<Integer>> subsets(int[] nums) {\n  List<List<Integer>> result = new ArrayList<>();\n  result.add(new ArrayList<>());  // empty set\n  for (int i = 0; i < nums.length; ++i) {\n    List<List<Integer>> newResult = new ArrayList<>(); // used for new lists\n    for (List<Integer> L : result) {\n      L = new ArrayList<>(L); // copy\n      L.add(nums[i]);\n      newResult.add(L);\n    }\n    result.addAll(newResult);  // concatenate\n  }\n  return result;\n}\n```\n\n**Time:** `O(N * 2^N)`\n- The outer loop takes `O(N)` time.\n- The inner loop takes `2, 4, 8, ..., 2^N` time respectively.\n- In inner loop, making a new copy of `L` takes at most `O(N)` time.\n- Total runtime `T(N) = N * (2 + 4 + 8 + ... + 2^N) ~= N * 2^N`\n\n**Space:** `O(N * 2^N)`\n\n\n\n### K-Size Subsets\n\nActually, we can use the code in [77. Combinations](https://www.junhaow.com/lc/problems/backtracking/77_combinations.html) to solve this problem.\n\n\n```java\npublic List<List<Integer>> subsets(int[] nums) {\n  List<List<Integer>> result = new ArrayList<>();\n  List<Integer> numList = new ArrayList<>();\n  \n  int n = nums.length;\n  for (int k = 0; k <= n; ++k) { // compatible with empty set\n    combine(n, k, 1, nums, numList, result);\n  }\n  return result;\n}\n\nprivate void combine(int n, int k, int d, int[] nums, List<Integer> numList, List<List<Integer>> result) {\n  // base case (in order to handle empty set, ordering of two IFs matters)\n  if (numList.size() == k) { // get a result\n    result.add(new ArrayList<>(numList));\n    return;\n  }\n  if (n - d + 1 < k - numList.size()) { // remaining elements are not enough\n    return;\n  }\n\n  for (int i = d; i <= n; ++i) {\n    int val = nums[i - 1];\n    numList.add(val);\n    combine(n, k, i + 1, nums, numList, result);\n    numList.remove(numList.size() - 1); // remove the last\n  }\n}\n```\n\n**Time:** `O(N * 2^N)`\n- `C(0, N) + C(1, N) + C(2, N) + C(3, N) + ... + C(N, N) = 2^N`\n\n**Space:** `O(N * 2^N)`\n\n\n## Subsets II\n\nReference:\n\n- [[Java] Two Way of Recursive thinking](https://leetcode.com/problems/subsets-ii/discuss/169226/Java-Two-Way-of-Recursive-thinking)\n- [Simple iterative solution](https://leetcode.com/problems/subsets-ii/discuss/30137/Simple-iterative-solution)\n\n> Given a collection of integers that might **contain duplicates**, `nums`, return all possible subsets (the power set).\n\n**Note:** The solution set must not contain duplicate subsets.\n\n```java\nInput: [1,2,2]\nOutput: [\n  [2],\n  [1],\n  [1,2,2],\n  [2,2],\n  [1,2],\n  []\n]\n```\n\n### Backtracking\n\nWe need to know when we **should not** add a list to the result list.\n\n![](https://bloggg-1254259681.cos.na-siliconvalley.myqcloud.com/wek92.jpg)\n\nBy observation, a duplicate list occurs when `offset >= 1` (when `offset = 0`, duplicate cannot occur) and `nums[offset - 1] == nums[offset]` and in the previous step we did not pick `nums[offset - 1]`. The information of whether it picks or not could be passed down by a **boolean parameter** `isPicked`.\n \nIf the above condition is satisfied:\n- Do not add the list to the result list.\n- Do not do the subproblem after picking the current element.\n- Only do the subproblem after not picking the current element.\n\n**Note:** Be careful where we should put the `numList.add(val)` and `numList.remove(numList.size() - 1)`.\n\n```java\npublic List<List<Integer>> subsetsWithDup(int[] nums) {\n  // sorting\n  Arrays.sort(nums);\n  \n  List<List<Integer>> result = new ArrayList<>();\n  List<Integer> numList = new ArrayList<>();\n  result.add(new ArrayList<>());\n  subsets(0, nums, numList, result, true);\n  return result;\n}\n\nprivate void subsets(int offset, int[] nums, List<Integer> numList, List<List<Integer>> result, boolean isPicked) {\n  // base case\n  if (offset >= nums.length) {\n    return;\n  }\n  int val = nums[offset];\n  // duplicate checking (convert && to ||)\n  if (offset == 0 || nums[offset - 1] != nums[offset] || isPicked == true) {\n    // pick\n    numList.add(val);\n    subsets(offset + 1, nums, numList, result, true);\n    result.add(new ArrayList<>(numList));  // add to the result list\n    numList.remove(numList.size() - 1);\n  }\n  // not pick\n  subsets(offset + 1, nums, numList, result, false);\n}\n```\n\nAnother version (similar): \n\n```java\nprivate void subsets(int offset, int[] nums, List<Integer> numList, List<List<Integer>> result, boolean isPicked) {\n  // base case\n  if (offset >= nums.length) {\n    return;\n  }\n  int val = nums[offset];\n  // not pick\n  subsets(offset + 1, nums, numList, result, false);\n  // duplicate check\n  if (offset >= 1 && nums[offset - 1] == nums[offset] && isPicked == false) {\n    return;\n  }\n  // pick\n  numList.add(val);\n  subsets(offset + 1, nums, numList, result, true);\n  result.add(new ArrayList<>(numList));  // add to the result list\n  numList.remove(numList.size() - 1); \n}\n```\n\n**Time:** `O(N * 2^N)`\n**Space:** `O(N * 2^N)`\n\n\n\n\n### Iteration\n\nUsing the same idea in backtracking, we need to figure out when we should add a list to the result list. Check out three examples below (`[1,2,3]`, `[1,2,2]`, `[5,5,5]`).\n\n![](https://bloggg-1254259681.cos.na-siliconvalley.myqcloud.com/y0inx.jpg)\n\nBy observation, we learn that we should start from, if duplicate is detected, a specific location in the result list. In Subsets I, we always start from $0$.\n\nInterestingly, the specific location corresponds to the initial size of the result list in the previous round. Since we change the result list in each round, we should cache the size of the result list as `cachedSize`.\n\nThen we denote the starting index as `startIdx`. In each round, similar to what we\'ve done in Subsets I, we set `startIdx` as:\n\n- `0` (no duplicate or `i == 0`)\n- `cachedSize` (duplicate occurs)\n\nAfter setting `startIdx`, remember to do the caching job for the current size of the result list. Notice a fact that this cached size may not be used in the next round.\n\n\n```java\npublic List<List<Integer>> subsetsWithDup(int[] nums) {\n  // sort\n  Arrays.sort(nums);\n  \n  List<List<Integer>> result = new ArrayList<>();\n  result.add(new ArrayList<>());  // empty set\n  \n  int cachedSize = 0, startIdx = 0;\n  for (int i = 0; i < nums.length; ++i) {\n    List<List<Integer>> newResult = new ArrayList<>();  // used for new lists\n    // set startIdx first before we update cachedSize\n    startIdx = (i > 0 && nums[i - 1] == nums[i]) ? cachedSize : 0; // if duplicate occurs\n    cachedSize = result.size(); // cache the size for startIdx in the next round\n    for (int j = startIdx; j < result.size(); ++j) {\n      List<Integer> L = result.get(j);\n      L = new ArrayList<>(L);  // copy\n      L.add(nums[i]);\n      newResult.add(L);\n    }\n    result.addAll(newResult);  // concatenate\n  }\n  return result;\n}\n```\n\n**Time:** `O(N * 2^N)`\n**Space:** `O(N * 2^N)`\n\n\n\n\n
['Backtracking', 'Recursion', 'Iterator', 'Java']