LeetCode [78] Subsets

78. Subsets

Medium

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],
  []
]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> ret; vector<int> cur; bt(nums, ret, cur, 0, nums.size()); return ret; } void bt(vector<int>& nums, vector<vector<int>>& ret, vector<int> &cur, int pos, int n){ if(pos==n){ ret.push_back(cur); return; } //not select num[pos] bt(nums, ret, cur, pos+1, n); //select num[pos] cur.push_back(nums[pos]); bt(nums, ret, cur, pos+1, n); cur.pop_back(); } }; class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { int n = nums.size(); vector<vector<int>> res; vector<int> cur; sort(nums.begin(), nums.end()); bt(nums, n, res, cur, 0); return res; } void bt(vector<int>& nums, int n, vector<vector<int>> &res, vector<int> cur, int index){ if(index>=n){ res.push_back(cur); return; } bt(nums, n, res, cur, index+1); cur.push_back(nums[index]); bt(nums, n, res, cur, index+1); } }; class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> ret; vector<int> cur; bt(nums, 0, nums.size(), cur, ret); return ret; } void bt(vector<int>& nums, int pos, int n, vector<int> &cur, vector<vector<int>> &ret){ ret.push_back(cur); for(int i=pos; i<n; ++i){ cur.push_back(nums[i]); bt(nums, i+1, n, cur, ret); cur.pop_back(); } } }; class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { int n = nums.size(); sort(nums.begin(), nums.end()); int N = pow(2, n); vector<int> cur; vector<vector<int>> res; for(int i=0; i<N; ++i){ cur.clear(); int mask = 1; for(int j=0; j<n; ++j){ if(mask&i){ cur.push_back(nums[j]); } mask = mask<<1; } res.push_back(cur); } return res; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { List<List<Integer>> lists; int n; public List<List<Integer>> subsets(int[] nums) { lists = new ArrayList<>(); n = nums.length; dfs(0, new ArrayList<>(), nums); return lists; } void dfs(int p, List<Integer> list, int[] nums){ if(p==n){ lists.add(list); }else{ dfs(p+1, list, nums); List<Integer> newList = new ArrayList<Integer>(list); newList.add(nums[p]); dfs(p+1, newList, nums); } } }