组合

//清晰简单的C++代码， DFS
class Solution {
public:
    void DFS(vector<vector<int>> &ret, vector<int> &path, int n, int start, int rest){
        if(!rest)
            ret.push_back(path);
        else{
            for(int i=start; i<=n-rest+1; ++i){
                path.push_back(i);
                DFS(ret, path, n, i+1, rest-1);
                path.pop_back();
            }
        }
    }
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> ret;
        vector<int> path;
        DFS(ret, path, n, 1, k);
        return ret;
    }
};

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > res;
        vector<int> ans;
        build(1,k,n,res,ans);
        return res;
    }
private:
    void build(int num,int k,int n,vector<vector<int> > &res,vector<int> &ans){
        if(k==0){
            res.push_back(ans);
            return;
        }
        if(num>n)return;
        //将该元素num放入组合集中，然后在剩下的n－1个数中再选择m－1个元素
        ans.push_back(num);
        build(num+1,k-1,n,res,ans);
        ans.pop_back();
        //不选择该元素，而从剩下的n－1个元素中选择m个元素
        build(num+1,k,n,res,ans);
    }
};

import java.util.ArrayList;
//使用剪枝对算法进行了优化；
//Your runtime beats 99.50 % of java submissions
public class Solution {
    private ArrayList<ArrayList<Integer>> res;

    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        res = new ArrayList<ArrayList<Integer>>();
        if (n <= 0 || k <= 0 || n < k)
            return res;
        generateCombinations(n, k, 1, new ArrayList<Integer>());

        return res;
    }

    private void generateCombinations(int n, int k, int start, List<Integer> list) {
        if (list.size() == k) {
            res.add(new ArrayList<Integer>(list));
            return;
        }
        if (start > n)
            return;

        int len = k - (list.size() + 1);
        //list当中最终应该有k个元素，当前元素为list.size() + 1，那么我们要为下次回溯留下足够多的数
        for (int i = start; i <= n - len; i++) {
            list.add(i);
            generateCombinations(n, k, i + 1, list);
            list.remove(list.size() - 1);
        }
    }

}

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> dp[k];
        for(int i = 1; i <= n - k + 1; i ++) {
            vector<int> v;
            v.push_back(i);
            dp[0].push_back(v);
        }
        for(int i = 1; i < k; i ++){
            for(auto it = dp[i-1].begin(); it != dp[i-1].end(); it++){
                vector<int> v = *it;
                for(int j = v.back() + 1; j <= n - k + i + 1; j++){
                    v.push_back(j);
                    dp[i].push_back(v);
                    v.pop_back();
                }
            }
        }
        return dp[k-1];
    }
};

//没用递归整的

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
    	vector<vector<int> > result;
    	vector<int> v;
    	Solve(1,n,k,result,v);
    	return result;
    }
    void Solve(int x,int n,int k,vector<vector<int> > &result,vector<int> &v)
    {
    	if(k==0)
    	{
    		result.push_back(v);
    		return;
		}
		if(x > n)
			return;
		v.push_back(x);
		Solve(x+1,n,k-1,result,v);
		v.pop_back();
		Solve(x+1,n,k,result,v);
	}
};

classSolution {
public:
         vector<vector<int> > vec;    // 要返回的 vector
    voidfun(vector<int> &vv,intii,intn,intk,intmx){  
  //用于递归的 函数    n 当前层数   k 最大层数 
        if(n == k){     //递归 到 结尾处 时 将 vv 添加到 vec 中
            vec.push_back(vv);
            return;
        }
        for(inti=ii+1;i<mx;i++){   //这一层 从 ii+1 开始 到 mx 结束
            vv[n] = i;
            fun(vv,i,n+1,k,mx+1);        // 下一层 从 i 开始 到 mx+1 处结束
        }
    }
    vector<vector<int> > combine(intn, intk) {
        vector<int> vv(k);       
        vec.clear();
        for(inti=1;i<n-k+2;i++){
            vv[0] = i;
            fun(vv,i,1,k,n-k+2+1);   
        }
        returnvec;
    }
};

class Solution {
public:
    vector<vector<int>> a;
    vector<vector<int> > combine(int n, int k) {
        vector<int> b;
        dfs(k,n,1,b);
        return a;
    }
    void dfs(int k,int n,int start,vector<int>& y) {  
        if(y.size()==k) {
            a.push_back(y);
            return ;
        }
        for(int i=start;i<=n-(k-y.size())+1;i++) {  //i的位置必须考虑集合中已有多少个元素，还差多少个元素，差（k-y.size()）个，I的位置就必须小于等于n-(k-y.size())+1
            y.push_back(i);
            dfs(k,n,i+1,y);
            y.pop_back();
        }
    }
};

//dfs爆搜所有结果
class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> >ans;
        if(n<k) return ans;
        vector<int>vec;
        for(int i=1;i<=n-k+1;++i)
        {
            vec.push_back(i);
            dfs(ans,vec,i,n,k,1);
            vec.pop_back();
        }
        return ans;    
    }
 private:
    void dfs(vector<vector<int> >&res,vector<int>sub,int index,int n,int k,int cnt)
    {
         if(cnt>=k){
             res.push_back(sub);
             return ;
         }
        for(int i=index+1;i<=n;++i)
        {
            sub.push_back(i);
            dfs(res,sub,i,n,k,cnt+1);
            sub.pop_back();
        }
        return ;
    }
};

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        getAllCombineList(1, n, k, new ArrayList<>());
        return res;
    }

    public void getAllCombineList(int start, int n, int k, ArrayList<Integer> list) {
        if(k == 0) {
            res.add(new ArrayList<>(list)); // 如果仅仅add(list)那么list.remove后,这个res也会减少 

            return;
        }

        for (int i = start; i <= n; i++) {
            list.add(i);
            getAllCombineList(i + 1, n, k - 1, list);
            list.remove(list.size() - 1);
        }

    }
}

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> res =  combineCore(n,k);
        //排序
        Collections.sort(res, (ArrayList<Integer> a,ArrayList<Integer> b)->{
            for(int i=0;i<a.size() && i<b.size();i++){
                if(a.get(i)!=b.get(i)){
                    return a.get(i).compareTo(b.get(i));
                }
            }
            return new Integer(a.size()).compareTo(b.size());
        });
        return res;
    }
    private ArrayList<ArrayList<Integer>> combineCore(int n, int k){
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(k>n || k==0){
            return res;
        }
        if(k==1){
            for(int i=1;i<=n;i++){
                ArrayList<Integer> resList = new ArrayList<>();
                resList.add(i);
                res.add(resList);
            }
            return res;
        }
        //n在组合内
        ArrayList<ArrayList<Integer>> nextRes1 = combineCore(n-1,k-1);
        for(ArrayList<Integer> nextResList : nextRes1){
            nextResList.add(n);
            res.add(nextResList);
        }
        //n不在组合内
        ArrayList<ArrayList<Integer>> nextRes2 = combineCore(n-1,k);
        res.addAll(nextRes2);
        
        return res;
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
    ArrayList<ArrayList<Integer>> resultList = new ArrayList<>();
    getAllCombineList(1, n, k, resultList, new ArrayList<>());

    return resultList;
    }
    
   public void getAllCombineList(int start, int n, int k,
      ArrayList<ArrayList<Integer>> resultList,
      ArrayList<Integer> list) {
    if (k == 0) {
      resultList.add(new ArrayList<>(list));
      return;
    }

    for (int i = start; i <= n; i++) {
      list.add(i);
      getAllCombineList(i + 1, n, k - 1, resultList, list);
      list.remove(list.size() - 1);
    }
  }
}

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

class Solution(object):
    def combine(self, n, k):
        if k == 0:
            return []
        elif k == 1:
            return [[i] for i in range(1, n + 1)]
        elif n == k:
            return [[i for i in range(1, n + 1)]]
        else:
            return self.combine(n - 1, k) + map(lambda x: x + [n], self.combine(n - 1, k - 1))

// 朴素回溯，每次都递归地从当前选中元素后面的元素中选
class Solution {
public:
    vector<vector<int>> res;

    void backTrace(vector<int>& temp, int n, int k, int index) {
        if (temp.size() == k) {
            res.push_back(temp);
            return;
        }
        for (int i = index; i <= n; i++) {
            temp.push_back(i);
            backTrace(temp, n, k, i + 1);
            temp.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<int> temp;
        backTrace(temp, n, k, 1);
        return res;
    }
};

## 二叉树思路，yes or no，是否添加当前index数据
## 递归添加当前路径
def binaryTreeSeq(nums,k,index,path,ans):
        if len(path)==k:
            ans.append(path)
            return 
        if index==len(nums):return
        
        no=path
        binaryTreeSeq(nums,k,index+1,no,ans)
        
        yes=path+[nums[index]]
        binaryTreeSeq(nums,k,index+1,yes,ans)
        
class Solution:
    def combine(self , n , k ):
        nums = list(range(1, n+1))
        ans=[]
        binaryTreeSeq(nums,k,0,[],ans)
        ans=ans[::-1]
        
        return(ans)
        # write code here

回溯：

//
// Created by jt on 2020/9/24.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param n int整型
     * @param k int整型
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > combine(int n, int k) {
        // write code here
        vector<vector<int>> res;
        vector<int> vec;
        backtrack(res, vec, n, k);
        return res;
    }
    void backtrack(vector<vector<int>> &res, vector<int> &vec,
            int n, int k) {
        if (vec.size() == k) { res.push_back(vec); return; }
        int start = vec.empty() ? 1 : vec[vec.size() - 1] + 1;
        for (int i = start; i <= n; ++i) {
            vec.push_back(i);
            backtrack(res, vec, n, k);
            vec.pop_back();
        }
    }
};