题意:给定含有重复数字的数组,求他所有的排列
题解:需要排序(为了去重),有一个vis数组,是用来判断当前位置的数字是否已经选过了。定义一个dfs,每一层dfs都是扫描整个数组,并且根据vis数组选数字。如果当前数组没有被vis过,那么可以添加到答案中。
去重:
if(i && nums[i-1] == nums[i] && !vis[i-1]) continue;
已知对于每一层dfs,我不能选择重复的数字,因为对于同一层dfs选择哪个重复的数字得到的答案一定是相同的
那如何知道我现在是在同一层?是当前的数字相邻的相同数字还没有被选中
class Solution {
public:vector<vector<int>> res;vector<vector<int>> permuteUnique(vector<int>& nums) {vector<int> tmp;vector<bool> vis(nums.size(), false);sort(nums.begin(), nums.end());dfs(nums, vis, tmp);return res;}void dfs(vector<int>& nums, vector<bool>& vis, vector<int>& tmp) {if(tmp.size() == nums.size()) {res.push_back(tmp);}for(int i = 0; i < nums.size(); i++) {if(i && nums[i-1] == nums[i] && !vis[i-1]) continue;if(!vis[i]) {vis[i] = true;tmp.push_back(nums[i]);dfs(nums, vis, tmp);tmp.pop_back();vis[i] = false;}}}
};
时间复杂度:指数级别
空间复杂度: O ( n ) O(n) O(n)
题意:给定一个数组,从数组中选数字,求所有和为target的组合,有重复数字
题解:需要排序,定义一个u,从第u位往后挑数字,如果和<= k,那就进入下一层dfs继续挑选
if(i > u && a[i] == a[i-1]) continue;
去除那些不在同一层的数字
class Solution {
public:vector<vector<int>> res;vector<vector<int>> combinationSum2(vector<int>& a, int t) {vector<int> tmp;sort(a.begin(), a.end());dfs(a, t, tmp, 0, 0);return res;}void dfs(vector<int>& a, int t, vector<int>& tmp, int u, int sum) {if( sum == t ) {res.push_back(tmp);}for(int i = u; i < a.size(); i++) {if(i > u && a[i] == a[i-1]) continue;if(sum + a[i] <= t) {tmp.push_back(a[i]);dfs(a, t, tmp, i+1, sum + a[i]);tmp.pop_back();}}}
};
时间复杂度:指数级别
空间复杂度: O ( n ) O(n) O(n)