77. Combinations

关联问题：排列1：46. Permutations， 排列2：47. Permutations II

问题：

给定1～n，拿出其中k个元素，进行组合，求可得到组合的所有可能。

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

Example 2:
Input: n = 1, k = 1
Output: [[1]]
 
Constraints:
1 <= n <= 20
1 <= k <= n

　　

解法：Backtracking（回溯算法）

对于本问题，两个变量：

• 路径：已经选择好的前几位结果path
• 选择列表：对该位置上元素的选择可能性：path的上一个元素 i + 1 ～ n

处理过程：

• base：递归退出条件：选择到最后一位结束，这里为已经选择好路径长度==给出的组合要求长度 k。
• 做选择：对于当前位置，选择其中一个可用数字a。
  • 路径.add(a)
  • 选择列表.delete(a)：上一个选择数字 i + 1
• 撤销选择：回退到选择数字a之前的状况。
  • 路径.delete(a)
  • 选择列表.add(a)：i

代码参考：

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