Summary of combination problems of Li Kou brush questions (backtracking)

 

77. Combine  

Given two integers  n  and  k, Return range  [1, n]  All the possibilities in  k  Combination of numbers .

You can press   In any order   Return to the answer .

class Solution {
private:
    vector<vector<int>> result; //  A collection of qualified results 
    vector<int> path; //  Used to store qualified results 
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            path.push_back(i); //  Processing nodes  
            backtracking(n, k, i + 1); //  recursive 
            path.pop_back(); //  to flash back , The node of undo processing 
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        result.clear(); //  Don't write 
        path.clear();   //  Don't write 
        backtracking(n, k, 1);
        return result;
    }
};

39. Combinatorial summation

To give you one No repeating elements Array of integers for  candidates And a target integer  target , find  candidates  You can make the sum of numbers as the target number  target Of all   Different combinations , And return... As a list . You can press In any order Return these combinations .

candidates Medium The same Numbers can Unlimited repeat selected . If the selected number of at least one number is different , Then the two combinations are different . 

For a given input , Guarantee and for  target The number of different combinations of is less than 150 individual .

Example  1：

Input ：candidates = [2,3,6,7], target = 7
Output ：[[2,2,3],[7]]
explain ：
2 and 3 Can form a set of candidates ,2 + 2 + 3 = 7 . Be careful 2 You can use it multiple times .
7 Is also a candidate , 7 = 7 .
Only these two combinations .

 

class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& candidates, int target,int begin){
    if(target<0) return;// prune   If the result after subtraction is less than 0, Then you will not get the result if you cut it later , And will not encounter recursive bases 
    if(target==0) {
        result.push_back(path);
        return;
    }// Recursive base   When put path The elements inside just make target be equal to 0 Stop recursion when 
    for(int i=begin;i<candidates.size();i++){
      path.push_back(candidates[i]);
      backtracking(candidates,target-candidates[i],i);
      path.pop_back();
    }// Single layer recursive logic   Notice that this is from begin At the beginning   It's not from 0 At the beginning   Because it's combination, not arrangement 
}
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    // sort(candidates.begin(),candidates.end());  If there are repeating elements   It needs to be sorted first   Then prune in the subsequent recursion 
    backtracking(candidates,target,0);
    return result;
    }
};

40. Combinatorial summation II

Given a set of candidate numbers  candidates  And a target number  target , find  candidates  All can make numbers and  target  The combination of .

candidates  Each number in can only be used in each combination   once  .

Be careful ： A solution set cannot contain duplicate combinations . 

class Solution {
public:
  vector<vector<int>> result;
  vector<int> path;
  void dfs(vector<int>& candidates, int target,int begin){
      if(target<0) return ;
      if(target==0) {
          result.push_back(path);
          return ;
      }
      for(int i=begin;i<candidates.size();i++){
        if (i > begin && candidates[i] == candidates[i - 1])
            continue;// Because each element can only appear once   Pruning operation   Otherwise, the element may be reused   For example, there are two elements 1  Then there may be [1,7],[1,7] Is the repeated solution 
          path.push_back(candidates[i]);
          dfs(candidates,target-candidates[i],i+1);
          path.pop_back();
          
      }
  }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(),candidates.end());
    dfs(candidates,target,0);
    return result;
    }
};

 216. Combinatorial summation III

Find the sum of all the sums  n Of  k  Combination of numbers , And the following conditions are met ：

Use only numbers 1 To 9
Every number   Use it once at most  
return A list of all possible valid combinations . The list cannot contain the same combination twice , Combinations can be returned in any order .

Example 1:

 Input : k = 3, n = 7
 Output : [[1,2,4]]
 explain :
1 + 2 + 4 = 7
 There is no other matching combination .

class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void backtracking(int n,int k,int index){
    int sum=0;   
    for(int i=0;i<path.size();i++) sum+=path[i];
    if(path.size()==k&&sum==n){
        result.push_back(path);
        return;
    }
    for(int i=index;i<=9;i++){
        path.push_back(i);
        backtracking(n,k,i+1);
        path.pop_back();// The beginning of traversal here is index instead of 0
    }
}
    vector<vector<int>> combinationSum3(int k, int n) {
    // result.clear(); //  Don't write 
    // path.clear();   //  Don't write 
    backtracking(n,k,1);
    return result;
    }
};

17. Letter combination of telephone number

Given a number only  2-9  String , Returns all the letter combinations it can represent . You can press In any order return .

The mapping of numbers to letters is given as follows （ Same as phone key ）. Be careful 1 Does not correspond to any letter .

 

Example 1：

 Input ：digits = "23"
 Output ：["ad","ae","af","bd","be","bf","cd","ce","cf"]

class Solution {
public:

vector<string> result;
vector<string> d={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void dfs(string &digits,int index,string  path){
    if(index==digits.size()){
    result.push_back(path);
    return;
    }
    int t=digits[index]-'0';// Must be reduced 0  Otherwise it's character ASCII Code is not 2 Corresponding 2
    for(int i=0;i<d[t].size();i++){
        path.push_back(d[t][i]);
        dfs(digits,index+1,path);
        path.pop_back();
    }
}
    vector<string> letterCombinations(string digits) {
    result.clear();
    if(digits.size()==0) return result;
    string path;
    dfs(digits,0,path);
    return result;
    }
};

46. Full Permutation

Give an array without duplicate numbers  nums , Back to its   All possible permutations  . You can   In any order   Return to the answer .

Example 1：

 Input ：nums = [1,2,3]
 Output ：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

 

class Solution {
public:
vector<int> path;
vector<vector<int>> result;
    vector<vector<int>> permute(vector<int>& nums) {
    vector<bool> used(nums.size(),false);
     dfs(nums,0,used);
     return result;
    }
void dfs(vector<int>& nums,int index,vector<bool>&used){
    if(nums.size()==path.size()){
    result.push_back(path);
    return;
    }
    for(int i=0;i<nums.size();i++){
        // if(i>0&&nums[i]==nums[i-1]&&used[i-1]==true){
        //     continue;
        // } An element can only be used once before pruning   And it needs to be sorted in advance 
     if(used[i]==false){
        used[i]=true;
        path.push_back(nums[i]);
        dfs(nums,i+1,used);
        path.pop_back();
        used[i]=false;
        }
    }

}

};

​​​​​​47. Full Permutation II

Given a sequence that can contain repeating numbers  nums , In any order   Returns all non repeating permutations .

 Input ：nums = [1,1,2]
 Output ：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

class Solution {
public:
vector<int> path;
vector<vector<int>> result;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    vector<bool> used(nums.size(),false);
    dfs(nums,0,used);
    return result;
    }
    void dfs(vector<int>& nums,int index,vector<bool>&used){
        if(nums.size()==path.size()){
            result.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==true){
                continue;
            }// Pruning operation   It needs to be sorted first 
            if(used[i]==false){
                used[i]=true;
                path.push_back(nums[i]);
                dfs(nums,i+1,used);
                path.pop_back();
                used[i]=false;
            }
        }
    }
};

 60. Arrange the sequence

Here's a string of parentheses and letters  s , Remove the minimum number of invalid parentheses , Make the input string valid .

Returns all possible results . You can press   In any order   return .

Give set  [1,2,3,...,n], All of its elements have  n! Species arrangement .

List all permutations in order of size , And mark one by one , When  n = 3 when , All arranged as follows ：

"123"
"132"
"213"
"231"
"312"
"321"
Given  n and  k, Back to page  k  Permutation .

class Solution {
public:
string path;
vector<string> result;
void dfs(int n,vector<bool> &used){
    if(path.size()==n){
        result.push_back(path);
        return;
    }
    for(int i=1;i<=n;i++){
    if (used[i] == true) continue;
        used[i]=true;
        path.push_back(i+'0');
        dfs(n,used);
        path.pop_back();
        used[i]=false;
    
    }
}
    string getPermutation(int n, int k) {
     vector<bool> used(n,false);
     dfs(n,used);
     return result[k-1];
    }
};

 78. A subset of

Give you an array of integers  nums , Elements in an array   Different from each other  . Returns all possible subsets of the array （ Power set ）.

Solution set   You can't   Contains a subset of repetitions . You can press   In any order   Returns the solution set .

Example 1：

 Input ：nums = [1,2,3]
 Output ：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void dfs(vector<int>& nums,int index){
    result.push_back(path);
    // if(index>=nums.size()) {
    //     return;
    // } There is no need to set the recursive base   Because in for After the end of the cycle   The recursion is over 
    
    for(int i=index;i<nums.size();i++){
        path.push_back(nums[i]);
        dfs(nums,i+1);
        path.pop_back();
    }
}
    vector<vector<int>> subsets(vector<int>& nums) {
    dfs(nums,0);
    return result;
    }
};

 90. A subset of II

 

Give you an array of integers nums , It may contain repeating elements , Please return all possible subsets of the array （ Power set ）.

Solution set You can't Contains a subset of repetitions . The solution set returned , Subsets can be classified by In any order array .

 Input ：nums = [1,2,2]
 Output ：[[],[1],[1,2],[1,2,2],[2],[2,2]]

class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void dfs(vector<int>& nums,int index){
    result.push_back(path);
    // if(index>=nums.size()) {
    //     return;
    // }
    
    for(int i=index;i<nums.size();i++){
        if (i>index&&nums[i] == nums[i - 1])
            continue;// Prioritize   Then prune 
        path.push_back(nums[i]);
        dfs(nums,i+1);
        path.pop_back();
    }
}
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    dfs(nums,0);
    return result;
    }
};