leetcode77. 组合

题目

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

示例 1：

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

示例 2：

输入：n = 1, k = 1
输出：[[1]]  

提示：

• 1 <= n <= 20
• 1 <= k <= n

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combinations

题解

首先画出树状图，理清思路，例如：n = 4, k = 2，

1. 以1为基准，和2，3，4组合，
2. 以2为基准，和3，4组合，
3. 以3为基准，和4组合
4. 以4为基准，结束组合

发现规律，基准数只与基准数后的数字依次组合，基准数<=n-k+1。利用回溯算法解题。

class Solution {

    private List<List<Integer>> res = new ArrayList();
    private LinkedList<Integer> queue = new LinkedList();

    public List<List<Integer>> combine(int n, int k) {
        backRecursive(1,n,k,0);
        return res;
    }

    public void backRecursive(int begin,int n,int k,int depth){
        if(depth==k){
            res.add(new ArrayList(queue));
            return;
        }
        depth++;
        //(n-(k-depth))是基准数结束条件
        for(int i=begin;i<=(n-(k-depth));i++){
            queue.offer(i);
            backRecursive(i+1,n,k,depth);
            //回溯到基准数
            queue.removeLast();
        }
    }
}