Commit433387e

applewjg

committed

Combinations

Change-Id: Ia12a15d4b921454d4356a022814c4d8172e0a175

1 parentd9759fa commit433387eCopy full SHA for 433387e

File tree

+42

-0

lines changed

+42

-0

lines changed

Lines changed: 42 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,42 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Dec 20, 2014`
	`4`	`+ Problem: Combinations`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: https://oj.leetcode.com/problems/combinations/`
	`7`	`+ Notes:`
	`8`	`+ Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.`
	`9`	`+ For example,`
	`10`	`+ If n = 4 and k = 2, a solution is:`
	`11`	`+ [`
	`12`	`+ [2,4],`
	`13`	`+ [3,4],`
	`14`	`+ [2,3],`
	`15`	`+ [1,2],`
	`16`	`+ [1,3],`
	`17`	`+ [1,4],`
	`18`	`+ ]`
	`19`	`+`
	`20`	`+ Solution: DFS.`
	`21`	`+ */`
	`22`	`+publicclassSolution {`
	`23`	`+publicList<List<Integer>>combine(intn,intk) {`
	`24`	`+List<List<Integer>>res =newArrayList<List<Integer>>();`
	`25`	`+ArrayList<Integer>path =newArrayList<Integer>();`
	`26`	`+combineRe(n,k,1,path,res);`
	`27`	`+returnres;`
	`28`	`+ }`
	`29`	`+voidcombineRe(intn,intk,intstart,ArrayList<Integer>path,List<List<Integer>>res){`
	`30`	`+intm =path.size();`
	`31`	`+if (m ==k) {`
	`32`	`+ArrayList<Integer>p =newArrayList<Integer>(path);`
	`33`	`+res.add(p);`
	`34`	`+return;`
	`35`	`+ }`
	`36`	`+for (inti =start;i <=n-(k-m)+1; ++i) {`
	`37`	`+path.add(i);`
	`38`	`+combineRe(n,k,i+1,path,res);`
	`39`	`+path.remove(path.size() -1);`
	`40`	`+ }`
	`41`	`+ }`
	`42`	`+}`

Comments

(0)