首页 > 代码库 > 【leetcode】Combinations
【leetcode】Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]
用DFS搜索一个森林，在搜索的过程中根据孩子的值必须大于父节点的值进行剪枝，森林的形状如下所示：
假设n=4，k=2；
代码如下：
1 public class Solution { 2 private void comb(int n,int k,int level,List<List<Integer>> answer,List<Integer> result){ 3 if(level == k){ 4 ArrayList<Integer> temp = new ArrayList<Integer>(result); 5 answer.add(temp); 6 7 return; 8 } 9 for(int i = 1;i <= n;i++){10 if(result.isEmpty() || result.get(result.size()-1) < i){11 result.add(i);12 comb(n, k, level+1, answer, result);13 result.remove(result.size()-1);14 }15 }16 }17 public List<List<Integer>> combine(int n, int k) {18 List<List<Integer>> answer = new ArrayList<List<Integer>>();19 List<Integer> result = new ArrayList<Integer>();20 21 comb(n, k, 0, answer, result);22 23 return answer;24 }25 }
level记录当前搜索的层次，等于k时说明找到了一个组合。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。