Subsets 解答

Question

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

Note:

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

For example,
If nums = [1,2,3], a solution is:

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

Solution 1 -- BFS

Because it's required that subset must be non-descending order, we can sort input array first. We can write out the solution space tree.

For example, input is [1,2,3]

　　　　　　[]

　　　　　/　|　

　　　[1] [2]　[3]

　　/　　　 |

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

If element of last level is [i, j, .., k], then we could traverse elements from [k + 1, .., last] to add one element to construct complete answers.

BFS can be easily implemented to solve this problem. Time complexity is size of solution space tree, ie, C_n⁰ + C_n¹+ C_n² + .. + C_n^n/2

 1 public class Solution {
 2     public List<List<Integer>> subsets(int[] nums) {
 3         Arrays.sort(nums);
 4         int length = nums.length;
 5         List<List<Integer>> results = new ArrayList<List<Integer>>();
 6         List<List<Integer>> current = new ArrayList<List<Integer>>();
 7         results.add(new ArrayList<Integer>());
 8         Map<Integer, Integer> map = new HashMap<Integer, Integer>();
 9         for (int i = 0; i < length; i++) {
10             map.put(nums[i], i);
11             List<Integer> tmp = new ArrayList<Integer>();
12             tmp.add(nums[i]);
13             current.add(tmp);
14             results.add(tmp);
15         }
16         while (current.size() > 0) {
17             List<List<Integer>> next = new ArrayList<List<Integer>>();
18             int l = current.size();
19             for (int i = 0; i < l; i++) {
20                 List<Integer> currentList = current.get(i);
21                 int ll = currentList.size();
22                 int last = currentList.get(ll - 1);
23                 int index = map.get(last);
24                 for (int j = index + 1; j < length; j++) {
25                     // Note: create a new object
26                     List<Integer> newList = new ArrayList<Integer>(currentList);
27                     newList.add(nums[j]);
28                     next.add(newList);
29                     results.add(newList);
30                 }
31             }
32             current = next;
33         }
34         return results;
35     }
36 }

Solution 2 -- DFS

We can transfer this problem to be list all combinations from number 0 to nums.length

And we can get combinations of each size by DFS. Same time complexity as solution 1.

 1 public class Solution {
 2     public List<List<Integer>> subsets(int[] nums) {
 3         Arrays.sort(nums);
 4         int length = nums.length;
 5         List<List<Integer>> results = new ArrayList<List<Integer>>();
 6         results.add(new ArrayList<Integer>());
 7         for (int i = 1; i <= length; i++) {
 8             dfs(nums, 0, results, new ArrayList<Integer>(), i);
 9         }
10         return results;
11     }
12     
13     private void dfs(int[] nums, int start, List<List<Integer>> results, List<Integer> list, int level) {
14         if (list.size() == level)
15             results.add(new ArrayList<Integer>(list));
16         for (int i = start; i < nums.length; i++) {
17             list.add(nums[i]);
18             dfs(nums, i + 1, results, list, level);
19             list.remove(list.size() - 1);
20         }
21     }
22 }