算法

(回溯) $O(2^n)$

对于这个问题，首先用枚举的思想，取一个子序列，每个数有两种状态，‘取’或者‘不取’。我们发现按顺序来枚举的话，有些前缀是相同的，所以这个问题可认为是一个n层的满二叉树上的状态，二叉树上某个节点，其左子树代表取这个数的状态，右子树代表不取这个数的状态。在递归的同时，用一个数组来记录路径上取的数的状态，最终获得所有组合。

C++ 代码

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> combination;
        vector<vector<int>> combinations;
        helper(1, combination, n, k, combinations);
        return combinations;
    }

    // 递归地求解问题
    // pos代表已访问到哪个数，combination代表当前地组合
    void helper(int pos, vector<int>& combination,
                int n, int k, vector<vector<int>>& combinations) {
        // 第一个递归出口，如果满足 k 个，将这种组合加入最终结果中
        if (combination.size() == k) {
            combinations.push_back(combination);
            return;
        }

        // 第二个递归出口，如果已访问完1 ~ n所有数字，退出当前函数
        if (pos == n + 1) {
            return;
        }

        // 可行性剪枝，如果后面的数都放入，个数不足k的话，退出
        if (combination.size() + n - pos + 1 < k) {
            return;
        }

        // 如果将当前数放入组合，将pos加入combination，继续递归
        combination.push_back(pos);
        helper(pos + 1, combination, n, k, combinations);
        // 递归结束后，弹出pos，还原状态
        combination.pop_back();

        // 不将pos加入combination的情况
        helper(pos + 1, combination, n, k, combinations);
    }
};

Java 代码

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

    public void dfs(int cur, int n, int k, List<Integer> temp, List<List<Integer>> res) {
        if (temp.size() == k) {
            res.add(new ArrayList<>(temp));
            return;
        }
        if (cur > n) return;
        temp.add(cur);
        dfs(cur + 1, n, k, temp, res);
        temp.remove(temp.size() - 1);
        dfs(cur + 1, n, k, temp, res);
    }
}