トピック/並べ替え、組合せ、サブセット問題の遡及

並べ替え、組み合わせのテーマの大部分は遡及法に用いられる.この部分には遡及法ではない問題も含まれている.まとめ:(1)遡及法は一般的に参照変数のみを含み,一時変数(2)の繰返し数を含まないハッシュテーブル判断(3)これらのタイプの問題は遡及時再帰の一環を用いて一般的に1層のループしかない.
一、組み合わせ
39.Combination Sumの組み合わせの和(重複する数はないが、同じ数が重複して現れる)
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

A solution set is: 
[
For example, given candidate set  [2, 3, 6, 7]  and target  7 , 

  [7],
  [2, 2, 3]
]

この問題の題意はsumシリーズと似ているが,要素の数は制限されていない.
自分の試みは、遡及法を使用して、難点は要素が繰り返し使用できることであり、コードが間違っていると、結果が繰り返される数は、2つの分岐が同時に行われ、重複する値が現れるためである.

class Solution {
public:
    vector> combinationSum(vector& candidates, int target) {
        vector> res;
        vector temp;
        if(candidates.size()==0) return res;
        std::sort(candidates.begin(),candidates.end());
        backStracking(candidates,target,res,temp,0);
        return res;
    }
   void backStracking(vector&nums,int target,vector>& res,vector& temp,int start){
        if(target==0){
            res.push_back(temp);

        } 
        if(target<0) return ;
        for(int i=start;i

正しい答え:2回目に前回繰り返した数の場合、再帰が完了すると、現在のループが自動的に現在の数の次に進むため、2つの再帰ブランチを設定する必要はありません.

class Solution {
public:
    vector> combinationSum(vector& candidates, int target) {
        vector> res;
        vector temp;
        if(candidates.size()==0) return res;
        std::sort(candidates.begin(),candidates.end());
        backStracking(candidates,target,res,temp,0);
        return res;
    }
   void backStracking(vector&nums,int target,vector>& res,vector& temp,int start){
        if(target==0){
            res.push_back(temp);
            return;
        } 
        if(target<0) return ;
        for(int i=start;i

40. Combination Sum II 
39との違いは、要素ごとに1回しか使用できないことであり、ここでの選択対象シーケンスで繰り返される可能性のある数の考え方は簡単である.ループのたびにハッシュテーブルを設定し、再帰中のiをi+1に変更するだけでよい.
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

For example, given candidate set  [10, 1, 2, 7, 6, 1, 5]  and target  8 ,  A solution set is: 

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

class Solution {
public:
    vector> combinationSum2(vector& candidates, int target) {
        vector> res;
        vector temp;
        if(candidates.size()==0) return res;
        std::sort(candidates.begin(),candidates.end());
        backStracking(candidates,target,res,temp,0);
        return res;
    }
   void backStracking(vector&nums,int target,vector>& res,vector& temp,int start){
        if(target==0){
            res.push_back(temp);
            return;
        } 
        if(target<0) return ;
       unordered_set flag;//       
        for(int i=start;i

77.Combinationsグループ
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.For example,If n = 4 and k = 2, a solution is:[  [2,4],
  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]

class Solution {
public:
    vector> combine(int n, int k) {
        vector> res;
        vector temp;
        comb(res,temp,1,k,n);
        return res;
    }
    void comb(vector>& res,vector temp,int start,int k,int n){
        if(k==0)
        {
            res.push_back(temp);
            return ; 
        }
        for(int i=start;i<=n-k+1;i++)
        {
            temp.push_back(i);
            comb(res,temp,i+1,k-1,n);
            temp.pop_back();
        }
            
                
    }
};

216. Combination Sum III
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
Input: k = 3, n = 7
Output:

[[1,2,4]]

Example 2:
Input: k = 3, n = 9
Output:

[[1,2,6], [1,3,5], [2,3,4]]

解法類似:

class Solution {
public:
    vector> combinationSum3(int k, int n) {
        vector> res;
        vector temp;
        comb(res,temp,1,n,k);
        return res;
    }
    void comb(vector>& res,vector& temp,int start,int n,int k){
        if(n==0&&k==0)
        {
            res.push_back(temp);
            return ;
        }
        if(k==0||n<0) return ;
        for(int i=start;i<=(n>9?9:n);i++)
        {
            temp.push_back(i);
            comb(res,temp,i+1,n-i,k-1);
            temp.pop_back();
        }
    }
};

377. Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers? http://blog.csdn.net/m0_37693059/article/details/77778398#t11ダイナミックプランニング
二、配列
46.Permutations配列問題剣38文字列の配列
すべての数字が異なる
Given a collection of distinct numbers, return all possible permutations.
For example, [1,2,3]  have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

この問題の説明は《剣》38を見てこれは1種の遡及方法です

class Solution {
public:
    vector> permute(vector& nums) {
        if(nums.size()==0) return res;
        permute(nums,0);
            return res;
    }
   void permute(vector & nums,int first){//nums    ，first         
        if(first==nums.size()) res.push_back(nums);
        for(int i=first;i & nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
       return ;
    }
    private:
    vector> res;//     ，            
};

47.Permutations II配列問題重複
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example, [1,1,2]  have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

考え方:47に基づいて、繰り返しの判断を加えて、直接スキップします.注意初めてループに入ると、比較の対象は自分自身で、このときはスキップできません.また、現在の数は異なる位置の同じ数と2回交換されません.
次のコードは問題があるようですが、通過できます.
答えにはたくさんの解法があるので、また見てみましょう.

class Solution {
public:
    vector> permuteUnique(vector& nums) {
        if(nums.size()==0) return res;
        permute(nums,0);
            return res;
    }
   void permute(vector & nums,int first){//nums    ，first         
        if(first==nums.size()) res.push_back(nums);
        unordered_set flag;
        for(int i=first;i & nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
       return ;
    }
    private:
    vector> res;//     ，            
};

31.Next Permutationダブルポインタ類似問題556.Next Greater Element III
私たちは数の辞書順(小さいから大きいまで)の概念を知っています.今、1つの配列を知っています.この数の次の辞書順の配列を返します.現在の配列が最後であれば、最小の配列を返します.後から前へ遍歴して、変更する位置はnums[i-1]がnums[i-1]をどの数で置き換えるかなど、最初に増加する位置です.ね.一番左のnums[i-1]より大きい数であるべきです(この数はnums[i]より小さいに違いありません.以前は増分または横ばいの順序だったので、そうでなければ、現在代替が必要な位置は前に見つかりました).置換後、nums[i-1]の位置が最も高く、例えば333555444333222、置換位置は35で、右側の最初の4を交換して、3345554433222になるべきです.
4の位置の後ろの数はできるだけ小さい数に並ぶべきで、もとは増加しないので、彼を反転するだけでいいです

class Solution {
public:
    void nextPermutation(vector& nums) {
        
        int n=nums.size();
        if(n<=1) return ;
        int left=n-1;
        int right=n-1;
        int posMin=n-1;
        while(left>0&&nums[left]<=nums[left-1])
        {
         left--;
        }
        if(left==0)//         
        {
            doReverse(nums,0,n-1);
            return ;
        }
        while(nums[right]<=nums[left-1])
            right--;
        swap(nums[right],nums[left-1]);
        doReverse(nums,left,n-1);
        return ;
                
    }
    void doReverse(vector& nums,int left,int right){
        while(left

60. Permutation Sequence
重複していない数のセットは、すべての配列でK番目に大きい数を返します.
私の考えは、通らないで、演算がタイムアウトするかもしれませんが、前の遡及法を使っています.

class Solution {
public:
    string getPermutation(int n, int k) {
        string nums(n,'0');
        int i=0;
        while(++i<=n)
        {
            nums.push_back('0'+i);
        }
        permute(nums,0,k);
        
        
    }
    void permute(string &nums,int start,int& k)
        {
         if(start==nums.size()-1)
         {
             k--;
        return ;
         } 
        for(int i=start;i

大神解法:
K番目の数を探して、私たちは彼の範囲を確定することができます.例えば、1,2,3,4番目の数を探しています.いずれかの数を取り出し、残りの数は3!個が並び、1と2で始まる数で上位12個を構成しています.
K番目の数は3-1,2,4で探して、前の12の数を除いて、まだ2つ残っていて、1,2,4、1つ出してからそれぞれ2があります!個が並んでいるので、2番目の数は1です.
具体的な考え方の参考:https://discuss.leetcode.com/topic/17348/explain-like-i-m-five-java-solution-in-o-n

class Solution {
public:
    string getPermutation(int n, int k) {
    string res;
        vector factorial(n+1,0);
        vector numbers;//             ，              list    
        int sum=1;
        factorial[0]=1;
        for(int i=1;i<=n;i++)
        {
            sum*=i;
            factorial[i]=sum;//      
            numbers.push_back(i);//      
        }
        k--;//    k  1，  numbers     0   
        for(int i=n-1;i>=0;i--)
        {
            int index=k/factorial[i];
            res.push_back('0'+numbers[index]);
            numbers.erase(numbers.begin()+index);
            k-=index*factorial[i];
            //if(k<0) break;     ，      ，       
        }
        return res;
    }
};

三、サブセット
78.Subsets重複数のないサブ数列を求め、剣38を拡張する
Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
详细解答:78.Subsets詳細
考え方1:反復方法.まず1文字1,2文字を考慮すると,1,2,12は新しい文字と前の組み合わせを含み,3番目の文字,1,2,12,3,13,23123に挿入される.

class Solution {
public:
    vector> subsets(vector& nums) {
        vector> res;
        vector temp;
        res.push_back(temp);
        if(nums.size()==0) return res;
        temp.push_back(nums[0]);
        res.push_back(temp);
        temp.clear();
        for(int i=1;i dingl=res[j];
                dingl.push_back(nums[i]);
                res.push_back(dingl);
            }
            
        }
        return res;
    }
};

構想2:ビットフラグを使用して、各文字が出現するか出現しないかはフラグビットで判断できる
配列の長さはnで,合計2^n個である.0~2^n個の数をとり、各数の各フラグビットが1であることを示すビットの数が含まれている.
二重ループをする.第1のレイヤループは各フラグビットに対して、第2のループはこの2^n個数に対してである.コードは次のとおりです.

class Solution {
public:
    vector> subsets(vector& nums) {
        //     ，                    
        int n=nums.size();
        int totalNum=pow(2,n);
        vector> res(totalNum,vector());
        for(int i=0;i>i&1)//          1
                    res[j].push_back(nums[i]);
            }
        }
        return res;
    }
};

考え方3:遡及再帰法

class Solution {
public:
    vector> subsets(vector& nums) {
     /*     ，             
                 ，         ，         ，        
       【123】     1 12 123-》pop（3）-》pop（2）-》 13 pop（3）-》pop(1)->2->23 ->pop(3) ->pop(3)->3
                 vector temp            
     
       ：vector  pop_back()
       */ 
        vector> res;
        vector temp;
        backStracking(nums,res,temp,0);
        return res;
    }
    void backStracking(vector& nums,vector>& res,vector& temp,int start){//   ，            ，      
        res.push_back(temp);
        for(int i=start;i

90.Subsets II重複数を含む場合の対処
処理方法は次のとおりです.
(1)まずソートする必要がある.
(2)再帰内のループについてハッシュテーブルを設定し,処理した数を保存する,すなわち,1つのループ内で重複する数に再帰を展開しないことを保証する.
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example, If nums =  [1,2,2] , a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

class Solution {
public:
    vector> subsetsWithDup(vector& nums) {
        //  ，         ，      
        std::sort(nums.begin(),nums.end());
           vector> res;
        vector temp;
        backStracking(nums,res,temp,0);
        return res;
    }
    void backStracking(vector& nums,vector>& res,vector& temp,int start){//   ，            ，      
        res.push_back(temp);
        unordered_set flag;
        for(int i=start;i