关联问题：排列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

 

代码参考：

 1 class Solution {
 2 public:
 3     void backtrack(vector<vector<int>>& res, vector<int>& path, int n, int k, int pos) {
 4         if(path.size() == k) {
 5             res.push_back(path);
 6             return;
 7         }
 8         for(int i=pos; i<=n; i++) {
 9             path.push_back(i);
10             backtrack(res, path, n, k, i+1);
11             path.pop_back();
12         }
13         return;
14     }
15     vector<vector<int>> combine(int n, int k) {
16         vector<vector<int>> res;
17         vector<int> path;
18         backtrack(res, path, n, k, 1);
19         return res;
20     }
21 };