给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

回溯+剪枝

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new ArrayList<>();Deque<Integer> path = new ArrayDeque<>();dfs(1,n,k,path,res);return res;}private void dfs(int begin,int n,int k,Deque<Integer> path,List<List<Integer>> res) {if(path.size() == k){res.add(new ArrayList<>(path));return;}//剪枝for(int i = begin; i <= n - (k-path.size())+1 ;i++){path.addLast(i);dfs(i+1,n,k,path,res);path.removeLast();}}
}