78. Subsets (Medium)
https://leetcode.com/problems/subsets/
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], [] ]
Solutions
1.
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> track = new ArrayList<>();
combine(0, nums, track, ans);
return ans;
}
private void combine(int depth, int[] nums, List<Integer> track, List<List<Integer>> ans) {
if (depth == nums.length) {
List<Integer> sol = new ArrayList<>(track);
ans.add(sol);
return;
}
track.add(nums[depth]);
combine(depth + 1, nums, track, ans);
track.remove(track.size()-1);
combine(depth + 1, nums, track, ans);
}
}
2.
class Solution2 {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
ans.add(new ArrayList<>());
int len = nums.length;
for (int i = 0; i < len; i++) {
int ansSize = ans.size();
for (int j = 0; j < ansSize; j++) {
List<Integer> sol = new ArrayList<>(ans.get(j));
ans.add(sol);
sol.add(nums[i]);
}
}
return ans;
}
}