77.组合

题目描述

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例：

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

思路

1.这道题可以使用回溯思想求解。
2.首先确定一个元素将其加入到容器中，然后对于其他元素也进行相同操作。
3.当容器内的元素等于k时便是递归结束的条件。
4.进行回溯操作，将原先确定的元素从容器内移除。

Java代码实现

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

    private void combine(int start,int n,int k,List<List<Integer>> res,List<Integer> cur) {
        //递归出口
        if(cur.size() == k){
            res.add(new ArrayList(cur));
            return ;
        }

        for (int i = start; i <= n; i++) {
            //固定该元素
            cur.add(i);
            //寻找k-1个其他元素的组合
            combine(i+1,n,k,res,cur);
            //回溯
            cur.remove(cur.size()-1);
        }
    }

Golang代码实现

func combine(n int, k int) [][]int {
    res := make([][]int,0)
    combineDG(1,n,k,[]int{},&res)
    return res
}

func combineDG(cur int,n int,k int,curNum []int, res *[][]int){
    if k == 0{
        copyNum := make([]int,len(curNum))
        copy(copyNum,curNum)
        *res = append(*res,copyNum)
        return
    }

    for i:=cur; i<=n ; i++ {
        curNum = append(curNum,i)
        combineDG(i+1,n,k-1,curNum,res)
        curNum = curNum[0:len(curNum)-1]
    }
}