77-组合

LeetCode 77. Combinations

LeetCode-77

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

method: 回溯

• 不能重复取，所以下一个要i+1

vector<vector<int>> ret;
vector<int> path;
void dfs(int n, int k, int index) {
    if (path.size() == k) {     // 取了k个，记录结果返回
        ret.push_back(path);
        return;
    }
    for (int i = index; i <= n - (k - path.size()) + 1; ++i) {
        path.push_back(i);
        dfs(n, k, i + 1);
        path.pop_back();
    }
}
vector<vector<int>> combine(int n, int k) {
    dfs(n, k, 1);
    return ret;
}

剪枝：现在已经取了path.size()个，还需要k-path.size()个，但是总共只有n个，所以必须从小于等于n-(k-path.size())+1开始取，超过这个范围就取不了k个了，+1是因为下标从1开始，如果从0开始就不用了
比如n=4,k=3，现在取了0个，接下来的取数不能大于4-(3-0)+1=2，也就是只可以从1,2开始取，超过2就取不到3个数了