Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/78.html
Given an integer array nums
of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
- All the numbers of
nums
are unique.
Algorithm
For the example [1,2,3]
given in the title,
- it is an empty set at the beginning,
- then we have to deal with 1, add 1 to the empty set, which is
[1]
, and now we have two selves[]
And[1]
, - let’s deal with 2, we add 2 to each of the previous subsets, and we can get
[2], [1, 2]
, then all the subsets are now[], [1], [2], [1, 2]
, - in the same way, we can get
[3], [1, 3], [2, 3], [1, 2, 3]
, plus all of previous the subsets
[]
[1]
[2]
[1 2]
[3]
[1 3]
[2 3]
[1 2 3]
Code
-
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Subsets { public class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> list = new ArrayList<>(); if (nums == null || nums.length == 0) { return list; } Arrays.sort(nums); // requirement: non-descending order // prepare, add empty one to start looping then. // @note: I forgot empty ArrayList<Integer> empty = new ArrayList<>(); list.add(empty); for (int i = 0; i < nums.length; i++) { int numToAdd = nums[i]; List<List<Integer>> newlyAddedList = new ArrayList<>(list); for (List<Integer> each : list) { ArrayList<Integer> newOne = new ArrayList<Integer>(each); // deep copy newOne.add(numToAdd); newlyAddedList.add(newOne); } list = newlyAddedList; } return list; } } class Solution_dfs { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); getAns(nums, 0, new ArrayList<>(), ans); return ans; } private void getAns(int[] nums, int start, ArrayList<Integer> temp, List<List<Integer>> ans) { ans.add(new ArrayList<>(temp)); // @note: deep copy for (int i = start; i < nums.length; i++) { temp.add(nums[i]); getAns(nums, i + 1, temp, ans); temp.remove(temp.size() - 1); } } } } ############ class Solution { private List<List<Integer>> ans = new ArrayList<>(); private int[] nums; public List<List<Integer>> subsets(int[] nums) { this.nums = nums; dfs(0, new ArrayList<>()); return ans; } private void dfs(int u, List<Integer> t) { if (u == nums.length) { ans.add(new ArrayList<>(t)); return; } dfs(u + 1, t); t.add(nums[u]); dfs(u + 1, t); t.remove(t.size() - 1); } }
-
// OJ: https://leetcode.com/problems/subsets/ // Time: O(N * 2^N) // Space: O(N) class Solution { public: vector<vector<int>> subsets(vector<int>& A) { vector<vector<int>> ans; vector<int> tmp; function<void(int)> dfs = [&](int i) { if (i == A.size()) { ans.push_back(tmp); return; } tmp.push_back(A[i]); dfs(i + 1); // Pick A[i] tmp.pop_back(); dfs(i + 1); // Skip A[i] }; dfs(0); return ans; } };
-
from typing import List class Solution: # bfs def subsets(self, nums: List[int]) -> List[List[int]]: if not nums: return [[]] nums.sort() # sort() not necessary if no duplicates result = [[]] for num in nums: result += [subset + [num] for subset in result] return result class Solution: # dfs def subsets(self, nums: List[int]) -> List[List[int]]: def dfs(u, t): ans.append(t[:]) # or, t.copy() for i in range(u, len(nums)): t.append(nums[i]) dfs(i + 1, t) t.pop() ans = [] nums.sort() # sort() not necessary if no duplicates dfs(0, []) return ans class Solution: # dfs, just pass down the final path def subsets(self, nums: List[int]) -> List[List[int]]: def dfs(nums, index, path, ans): ans.append(path) [dfs(nums, i + 1, path + [nums[i]], ans) for i in range(index, len(nums))] ans = [] dfs(nums, 0, [], ans) return ans class Solution: # dfs, but running slower, since need to reference from parent method for 'nums' and 'ans' def subsets(self, nums: List[int]) -> List[List[int]]: def dfs(index, path): ans.append(path) [dfs(i + 1, path + [nums[i]]) for i in range(index, len(nums))] ans = [] dfs(0, []) return ans
-
func subsets(nums []int) [][]int { var ans [][]int var dfs func(u int, t []int) dfs = func(u int, t []int) { if u == len(nums) { ans = append(ans, append([]int(nil), t...)) return } dfs(u+1, t) t = append(t, nums[u]) dfs(u+1, t) t = t[:len(t)-1] } var t []int dfs(0, t) return ans }
-
function subsets(nums: number[]): number[][] { const n = nums.length; const t: number[] = []; const res: number[][] = []; const dfs = (i: number) => { if (i === n) { res.push([...t]); return; } dfs(i + 1); t.push(nums[i]); dfs(i + 1); t.pop(); }; dfs(0); return res; }
-
impl Solution { fn dfs(i: usize, t: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, nums: &Vec<i32>) { if i == nums.len() { res.push(t.clone()); return; } Self::dfs(i + 1, t, res, nums); t.push(nums[i]); Self::dfs(i + 1, t, res, nums); t.pop(); } pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> { let mut res = Vec::new(); Self::dfs(0, &mut Vec::new(), &mut res, &nums); res } }