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], [] ]
题意：
给定一个含不同整数的集合，返回其所有的子集
assumption:
1. do we need to return if subsets is empty?
2. what kind of order to return if there are many subsets
3. dupulicates in the given array?
solution:
1.
example:
nums = [1, 2, 3]
^
index
level0 [ ]
/ | \
level1 [1] [2] [3]
/ \
level2 [1,2] [1,3]
/
level3 [1,2,3]
level0: add [] to result[ [] ], use pointer: index to scan given array, add current element to path [1], pass [1] to next level,
level1: add[1] to result[[][1]], treat index element as a start, pick one in the remaining and added to the path [1,2], pass[1,2] to next level
level2: add[1,2] to result[[][1][1,2]] treat index element as a start, pick one in the remaining and added to the path [1,2, 3], pass[1,2,3] to next level
level3: add[1,2,3] to result[[][1][1,2][1,2,3]]
二、High Level带着面试官walk through：
生成ArrayList作为每条path的记录，扔到result里
以当前index为开头，call helper function, 使得在index之后剩下可用的item中选一个加到当前path后面
代码：
1 class Solution { 2 public List<List<Integer>> subsets(int[] nums) { 3 List<List<Integer>> result = new ArrayList<>(); 4 List<Integer> path = new ArrayList<>(); 5 helper(nums,0, path, result); 6 return result; 7 } 8 private void helper(int[]nums, int index, List<Integer> path, List<List<Integer>> result){ 9 result.add(new ArrayList<>(path)); 10 11 for(int i = index; i< nums.length; i++){ 12 path.add(nums[i]); 13 helper(nums, i+1, path, result); 14 path.remove(path.size()-1); 15 } 16 } 17 }
转载于:https://www.cnblogs.com/liuliu5151/p/9190029.html
