题目
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1 输出：[[1]]
提示：
- 1 <= n <= 20
- 1 <= k <= n
解题
方法一：回溯
class Solution { public: vector<vector<int>> res; vector<int> path; void backtracing(int n,int k,int startIndex){ if(path.size()==k){ res.push_back(path); return; } for(int i=startIndex;i<=n;i++){ path.push_back(i); backtracing(n,k,i+1); path.pop_back(); } } vector<vector<int>> combine(int n, int k) { backtracing(n,k,1); return res; } };
剪枝后的结果
class Solution { public: vector<vector<int>> res; vector<int> path; void backtracing(int n,int k,int startIndex){ if(path.size()==k){ res.push_back(path); return; } for(int i=startIndex;i<=n-(k-path.size())+1;i++){ //优化部分 path.push_back(i); backtracing(n,k,i+1); path.pop_back(); } } vector<vector<int>> combine(int n, int k) { backtracing(n,k,1); return res; } };
java
class Solution { List<List<Integer>> res=new LinkedList<>(); List<Integer> path=new LinkedList<>(); void dfs(int startIndex,int n,int k){ if(path.size()==k){ res.add(new LinkedList<>(path)); return; } for(int i=startIndex;i<=n;i++){ path.add(i); dfs(i+1,n,k); path.remove(path.size()-1); } } public List<List<Integer>> combine(int n, int k) { dfs(1,n,k); return res; } }
