1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 回溯法
    pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
        fn backtrace(n: i32, k: i32, start: i32, tmp: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
            if tmp.len() as i32 == k {
                res.push(tmp.clone());
                return;
            }
            for i in start..=n {
                tmp.push(i as i32);
                backtrace(n, k, i + 1, tmp, res);
                tmp.pop();
            }
        }

        let mut res = vec![];
        let mut tmp = vec![];

        backtrace(n, k, 1, &mut tmp, &mut res);

        res
    }
}
// @lc code=end

struct Solution;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    vector<vector<int>> result;
public:
    /*
    * ## 解题思路
    * * 深度遍历
    */
    vector<vector<int>> combine(int n, int k) {
        vector<int> tmp;
        dfs(tmp, n, k, 1);
        return result;
    }

    void dfs(vector<int>& tmp, int total, int left, int start) {
        if (left == 0 ) {
            result.push_back(tmp);
            return;
        }

        // 如果当前数字小于tmp中已存在的最大值，则跳过，继续下一个字符
        for(int i=start; i<=total; i++) {
            // 将当前数字加入tmp
            tmp.push_back(i);
            // 从下一个数开始，深度遍历下一个
            dfs(tmp, total, left-1, i+1);
            // 回退当前所选数
            tmp.pop_back();
        }
    }
};