[DFS "want" or "don't"] seek subsets; Seeking combination

Find all subsets of a sequence .

General train of thought ：
Also use dfs To do the , Because it's actually “ want ” or “ Don't ” The problem of , This is a dfs Typical problems that can be solved ！

Be careful ：sort(start,end, Sorting method ), Generally speaking end=start+size(), however vector Yes .begin and .end() Just use the pointer .

       vector Of push_back Is to add elements to the end , that pop_back Delete the last element ！

AC Code ：

class Solution {
    
public:
    vector<vector<int> > subsets(vector<int> &S) {
    
        vector<vector<int> > subs;
        vector<int> sub;
        sort(S.begin(),S.end());
        dfs(S,subs,sub,0);
        return subs;
    }
    
    void dfs(vector<int> S,vector<vector<int> >&subs,vector<int> sub,int start)
    {
    
        subs.push_back(sub);
        for(int i=start;i<S.size();i++)
        {
    
            sub.push_back(S[i]); // want 
            dfs(S,subs,sub,i+1);
            sub.pop_back(); // Don't  （ Pay attention to this sub It's value passing , therefore pop_back Can ）
        }
    }
    
};

Empathy ,“ want ” or “ Don't ” Combinatorial problem ：

Here you are. n,k, Output 1~n in k Combination of numbers .

class Solution {
    
public:
    vector<vector<int> > res;
    vector<vector<int> > combine(int n, int k) {
    
        if(n<k)
            return res;
        if(n==0 || k==0)
            return res;
        vector<int> cur;
        for(int i=1;i<=n;i++)
        {
    
            cur.push_back(i);
            dfs(n,k,i,1,cur);
            cur.pop_back();
        }
        return res;
    }
    
    void dfs(int n,int k,int start,int times,vector<int> cur) //start The current number ,times What is the current number 
    {
     //start Has joined cur
        if(times==k)
        {
    
            res.push_back(cur);
            return;
        }
        for(int i=start+1;i<=n;i++)
        {
    
            // want 
            cur.push_back(i);
            dfs(n,k,i,times+1,cur);
            // Don't 
            cur.pop_back();
        }
    }
};