Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/78.html
78. Subsets
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 = [1,2,3], a solution is:
[
[],
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2]
]
@tag-array
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() 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(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 ############ class Solution(object): def subsets(self, nums): """ :type nums: List[int] :rtype: 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
-
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 } }