學習要點

? ? ? ? 學習回溯思想，學習回溯技巧；大家應當先看一下下面這幾道題

1. leetcode：46. 全排列-CSDN博客
2. leetcode：78. 子集-CSDN博客
3. leetcode：90. 子集 II-CSDN博客

題目鏈接

????????77. 組合 - 力扣（LeetCode）

題目描述

解法：回溯

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

解析

1. 先添加有1的
2. 再添加有2，但是沒有1的
3. 再添加有3，但是沒有1和2的
4. 以此類推