Combinations leetcode java

1657 ワード

タイトル:
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(Work BreakII参照)のループ再帰的にサブ問題を処理する方法で解決する.nはループの回数であり,kは各試行の異なる数字である.遡及に用いた.
コードは次のとおりです.
 
 1     
public ArrayList> combine(
int n, 
int k) {
 2         ArrayList> res = 
new ArrayList>();
 3         
if(n <= 0||n < k)
 4             
return res;
 5         ArrayList item = 
new ArrayList();    
 6         dfs(n,k,1,item, res);
//
because it need to begin from 1
 7 
        
return res;
 8     }
 9     
private 
void dfs(
int n, 
int k, 
int start, ArrayList item, ArrayList> res){
10         
if(item.size()==k){
11             res.add(
new ArrayList(item));
//
because item is ArrayList so it will not disappear from stack to stack
12 
            
return;
13         }
14         
for(
int i=start;i<=n;i++){
15             item.add(i);
16             dfs(n,k,i+1,item,res);
17             item.remove(item.size()-1);
18         }
19     }
Reference:http://blog.csdn.net/linhuanmars/article/details/21260217