Viggo的小屋 2019-06-28
这道题重定义了什么叫可行解:
一般而言,可行解需要满足强约束性条件集,而本题的可行解就是单一弱约束性条件(distinct integers,只需要当前集合内的元素不重复即可算作一个可行解) ,算是比较简单的入门级dfs + backtracing 题目。
class Solution { public: void dfs(vector<vector<int>> & vct,vector<int> &cur,vector<int>& nums,int index) { vct.push_back(cur); int n = nums.size(); if(index >= n) return; for(int i = index;i < n;++i) { cur.push_back(nums[i]); dfs(vct,cur,nums,i + 1); cur.pop_back(); } } vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> vct; vector<int> cur; dfs(vct,cur,nums,0); return vct; } };
diff vs the pre version:
有重复的元素怎么算?相关的思路雷同于Leetcode - 040. Combination Sum II
class Solution { public: void dfs(vector<vector<int>> &vct, vector<int> &cur, vector<int>& nums,vector<int> & used,int index) { vct.push_back(cur); int n = nums.size(); if (index >= n) return; for (int i = index; i < n; ++i) { if (used[i] == 0) { int j = i - 1; bool repeated = false; while (j >= 0 && nums[j] == nums[i]) { if (used[j] == 0) { repeated = true; break; } --j; } if (repeated) continue; cur.push_back(nums[i]); used[i] = 1; dfs(vct, cur, nums, used, i + 1); used[i] = 0; cur.pop_back(); } } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { vector<vector<int>> vct; vector<int> cur; int n = nums.size(); if (n <= 0) return vct; vector<int> used(n, 0); sort(nums.begin(), nums.end()); dfs(vct, cur, nums,used,0); return vct; } };