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 =
If nums =
[1,2,3]
, a solution is:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
Solution 1, also a combination problem not permutation.
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res=new ArrayList<>();
List<Integer> one=new ArrayList<>();
Arrays.sort(nums);
dfs(0,nums,one,res);
return res;
}
private void dfs(int d, int[]nums, List<Integer> one, List<List<Integer>> res) {
res.add(new ArrayList<Integer>(one));
for (int i=d; i<nums.length; i++) {
one.add(nums[i]);
dfs(i+1,nums,one,res);
one.remove(one.size()-1);
}
}
}
Solution 2, another way to wring the code.
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res=new ArrayList<>();
List<Integer> one=new ArrayList<>();
Arrays.sort(nums);
dfs(0,nums,one,res);
return res;
}
private void dfs(int d, int[]nums, List<Integer> one, List<List<Integer>> res) {
if (d==nums.length) res.add(new ArrayList<Integer>(one));
else {
dfs(d+1,nums,one,res);
one.add(nums[d]);
dfs(d+1,nums,one,res);
one.remove(one.size()-1);
}
}
}
没有评论:
发表评论