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后面
代码:
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
helper(nums,0, path, result);
return result;
}
private void helper(int[]nums, int index, List<Integer> path, List<List<Integer>> result){
result.add(new ArrayList<>(path)); for(int i = index; i< nums.length; i++){
path.add(nums[i]);
helper(nums, i+1, path, result);
path.remove(path.size()-1);
}
}
}