附近2公里招临时工_青创网石狮服装批发网_推广团队_关键词搜索量查询工具

题意：给定含有重复数字的数组，求他所有的排列

题解：需要排序（为了去重），有一个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)$

题意：给定一个数组，从数组中选数字，求所有和为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)$