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时说明找到了一个组合。
【leetcode】Combinations,布布扣,bubuko.com
原文：http://www.cnblogs.com/sunshineatnoon/p/3851953.html