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:
この問題は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
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
int n,
int k) {
2 ArrayList
new ArrayList
3
if(n <= 0||n < k)
4
return res;
5 ArrayList
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
10
if(item.size()==k){
11 res.add(
new ArrayList
//
because item is ArrayList
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