当前位置:网站首页>Some thoughts on backtracking to find permutations and combinations

Some thoughts on backtracking to find permutations and combinations

2022-09-23 08:53:24leimingzeOuO

结论

组合是start,排列是0和st[].
if(i!=x&&c[i]==c[i-1])continue;is to prevent two equal numbers from being placed in the same position(same level of tree)
排列:-->st[]
		[1,6]!=[6,1].-->for(int i=0;i<n;i++)
		不重复:Only one equal number can be placed in the same position-->if(i&&c[i]==c[i-1]&&!st[i-1])continue
组合:
		[1.6]==[6,1]--->for(int i=start;i<n;i++)
		不重复:if(i!=start&&c[i]==c[i-1])continue;

46. 全排列

First is the most classic permutations
1

class Solution {
    
public:
    int n;
    vector<vector<int>>res;
    vector<bool>st;
    vector<int>v;
    void dfs(int u,vector<int>&nums)
    {
    
        if(u>=n)
        {
    
            res.push_back(v);
            return;
        }
        for(int i=0;i<n;i++)
        {
    
            if(st[i])continue;
            st[i]=true;
            v.push_back(nums[i]);
            dfs(u+1,nums);
            st[i]=false;
            v.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
    
        n=nums.size();
        st.resize(n);
        dfs(0,nums);
        return res;
    }
};

39. 组合总和

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IqltASNF-1663860261696)(h ttps://img-blog.csdnimg.cn/86f56cee5d3e4293af3befd76b1f7bbb.png)

First of all, it can be seen that this question is a“完全背包问题”求具体方案,we use violencedfs来做.常规的dfs:

void dfs(int u)

这里的uenumerates the location
但是这个题,如果我们uenumeration enumeration empty words,There is no way to deduplicate according to the requirements of the topic.
So let's change an angle here,uEnumerate each number in an array,Then enumerate the number of each number.
在这里插入图片描述

    vector<vector<int>>res;
    vector<int>v;
    void dfs(int u,vector<int>&c,int target)
    {
    
        if(!target)
        {
    
            res.push_back(v);
            return;
        }
        if(u==c.size())return;
        for(int i=0;c[u]*i<=target;i++)//Enumerate the number of possible selections for each number
        {
    
            for(int j=0;j<i;j++)v.push_back(c[u]);
            dfs(u+1,c,target-c[u]*i);
            for(int j=0;j<i;j++)v.pop_back();
        }
    }

40. 组合总和 II

在这里插入图片描述
题目要求:

  1. 每个数字在每个组合中只能使用一次
  2. The solution set cannot contain duplicate combinations
    这里划重点了.不能有重复的组合,比如[6,1,1]和[1,1,6]不能同时存在,So here are the first details,Enumerations should start from the previous
for(int i=0;i<n;i++)

should be converted to

for(int i=start;i<n;i++)

The purpose is to prevent duplication caused by selecting the previous number
第二个细节:[1,1,6],sum=7,结果只能是[1,6],So there is also a heavy

if(i!=start&&c[i]==c[i-1])continue;

what is this step?
其实这个题,The main difference from the first question is that this question enumerates vacancies,If there are equal numbers in the same position,should be deleted.
在这里插入图片描述

Of course, the prerequisite is thatsort排序so that we can.

class Solution {
    
public:
    vector<vector<int>>res;
    vector<int>v;
    void dfs(int start,vector<int>&c,int target)
    {
    
        if(target<0)return;
        if(target==0)
        {
    
            res.push_back(v);
            return;
        }
        for(int i=start;i<c.size();i++)
        {
    
            if(i!=start&&c[i]==c[i-1])continue;
            v.push_back(c[i]);
            dfs(i+1,c,target-c[i]);
            v.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    
        sort(candidates.begin(),candidates.end());
        dfs(0,candidates,target);
        return res;
    }
};

47. 全排列 II

在这里插入图片描述

不重复的全排列,[1,2]与[2,1]是不同的,So here there is no need fromstart开始枚举,So what is going on in the end??

  	if(st[i])continue;
 	if(i&&p[i]==p[i-1]&&!st[i-1])continue;
  1. First of all, why use a weighted array here??
    Because every time he fromi=0开始遍历,Prevent numbers in a position from being reused.
  2. 为什么要加上!st[i-1]
    当枚举到i是,In the same layer of the treei-1state is restored tofalse,当前位置u其实已经被i-1of numbers have been repeated.
class Solution {
    
public:
    int n;
    vector<bool>st;
    vector<int>v;
    vector<vector<int>>res;
    void dfs(int u,vector<int>&p)
    {
    
        if(v.size()==n)
        {
    
            res.push_back(v);
            return;
        }
        for(int i=0;i<n;i++)
        {
    
            if(st[i])continue;
            if(i&&p[i]==p[i-1]&&!st[i-1])continue;
            st[i]=true;
            v.push_back(p[i]);
            dfs(u+1,p);
            v.pop_back();
            st[i]=false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
    
        sort(nums.begin(),nums.end());
        n=nums.size();
        st.resize(nums.size());
        dfs(0,nums);
        return res;
    }
};

90. 子集 II

在这里插入图片描述

class Solution {
    
public:
    vector<vector<int>>res;
    vector<int>v;
    void dfs(int start,vector<int>&c)
    {
    
        res.push_back(v);
        for(int i=start;i<c.size();i++)
        {
    
            if(i>start&&c[i]==c[i-1])continue;
            v.push_back(c[i]);
            dfs(i+1,c);
            v.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    
        sort(nums.begin(),nums.end());
        dfs(0,nums);
        return res;
    }
};
原网站

版权声明
本文为[leimingzeOuO]所创,转载请带上原文链接,感谢
https://chowdera.com/2022/266/202209230847287823.html

随机推荐