Commitc6366ce

committed

add a solution for 46

1 parenta962eed commitc6366ceCopy full SHA for c6366ce

File tree

+33

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _46.java
- test/java/com/fishercoder
  - _46Test.java

+33

-0

lines changed

Lines changed: 29 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -68,4 +68,33 @@ private void backtracking(List<Integer> list, int[] nums, Set<List<Integer>> ans`
`68`	`68`	`}`
`69`	`69`	`}`
`70`	`70`
	`71`	`+publicstaticclassSolution3 {`
	`72`	`+/**`
	`73`	`+ * A more efficient version of backtracking.`
	`74`	`+ */`
	`75`	`+publicList<List<Integer>>permute(int[]nums) {`
	`76`	`+List<List<Integer>>ans =newArrayList<>();`
	`77`	`+boolean[]used =newboolean[nums.length];`
	`78`	`+returnbacktracking(ans,used,newArrayList<>(),nums);`
	`79`	`+ }`
	`80`	`+`
	`81`	`+privateList<List<Integer>>backtracking(List<List<Integer>>ans,boolean[]used,List<Integer>list,int[]nums) {`
	`82`	`+if (list.size() ==nums.length) {`
	`83`	`+ans.add(newArrayList<>(list));`
	`84`	`+returnans;`
	`85`	`+ }`
	`86`	`+for (inti =0;i <nums.length;i++) {`
	`87`	`+if (used[i]) {`
	`88`	`+continue;`
	`89`	`+ }`
	`90`	`+used[i] =true;`
	`91`	`+list.add(nums[i]);`
	`92`	`+backtracking(ans,used,list,nums);`
	`93`	`+used[i] =false;`
	`94`	`+list.remove(list.size() -1);`
	`95`	`+ }`
	`96`	`+returnans;`
	`97`	`+ }`
	`98`	`+ }`
	`99`	`+`
`71`	`100`	`}`

Lines changed: 4 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -8,22 +8,26 @@`
`8`	`8`	`publicclass_46Test {`
`9`	`9`	`privatestatic_46.Solution1solution1;`
`10`	`10`	`privatestatic_46.Solution2solution2;`
	`11`	`+privatestatic_46.Solution3solution3;`
`11`	`12`
`12`	`13`	`@BeforeClass`
`13`	`14`	`publicstaticvoidsetup() {`
`14`	`15`	`solution1 =new_46.Solution1();`
`15`	`16`	`solution2 =new_46.Solution2();`
	`17`	`+solution3 =new_46.Solution3();`
`16`	`18`	`}`
`17`	`19`
`18`	`20`	`@Test`
`19`	`21`	`publicvoidtest1() {`
`20`	`22`	`CommonUtils.printListList(solution1.permute(newint[]{1,2,3}));`
`21`	`23`	`CommonUtils.printListList(solution2.permute(newint[]{1,2,3}));`
	`24`	`+CommonUtils.printListList(solution3.permute(newint[]{1,2,3}));`
`22`	`25`	`}`
`23`	`26`
`24`	`27`	`@Test`
`25`	`28`	`publicvoidtest2() {`
`26`	`29`	`CommonUtils.printListList(solution1.permute(newint[]{1,2,3,4,5,6}));`
`27`	`30`	`CommonUtils.printListList(solution2.permute(newint[]{1,2,3,4,5,6}));`
	`31`	`+CommonUtils.printListList(solution3.permute(newint[]{1,2,3,4,5,6}));`
`28`	`32`	`}`
`29`	`33`	`}`

Comments

(0)