Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf0bfc2f

Browse files
add a solution for 698
1 parent20fede4 commitf0bfc2f

File tree

2 files changed

+108
-1
lines changed

2 files changed

+108
-1
lines changed

‎src/main/java/com/fishercoder/solutions/_698.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
packagecom.fishercoder.solutions;
22

3+
importjava.util.Arrays;
4+
35
publicclass_698 {
46

57
publicstaticclassSolution1 {
@@ -38,4 +40,56 @@ private boolean canPartition(int[] nums, boolean[] visited, int startIndex, int
3840
}
3941
}
4042

43+
publicstaticclassSolution2 {
44+
/**
45+
* I'm glad that I figured out below solution completely on my own on 9/30/2021.
46+
* Backtracking is so beautiful!
47+
* <p>
48+
* Although not super concise, and I've added a sorting step, it's completely original.
49+
*/
50+
publicbooleancanPartitionKSubsets(int[]nums,intk) {
51+
Arrays.sort(nums);
52+
longsum =0l;
53+
for (intnum :nums) {
54+
sum +=num;
55+
}
56+
intave = (int)sum /k;
57+
if (sum %k !=0) {
58+
returnfalse;
59+
}
60+
boolean[]used =newboolean[nums.length];
61+
intfound =0;
62+
for (inti =nums.length -1;i >=0;i--) {
63+
if (!used[i]) {
64+
used[i] =true;
65+
found +=recursive(nums,used,ave,nums[i],i);
66+
}
67+
}
68+
returnk ==found;
69+
}
70+
71+
privateintrecursive(int[]nums,boolean[]used,inttargetSum,intcurrSum,intcurrIndex) {
72+
if (currSum ==targetSum) {
73+
return1;
74+
}elseif (currSum >targetSum) {
75+
used[currIndex] =false;
76+
return0;
77+
}else {
78+
if (currIndex >0) {
79+
for (inti =currIndex;i >0;i--) {
80+
if (!used[i -1]) {
81+
used[i -1] =true;
82+
intfound =recursive(nums,used,targetSum,currSum +nums[i -1],i -1);
83+
if (found ==1) {
84+
returnfound;
85+
}
86+
used[i -1] =false;//this is the backtracking step: reset this number to be available if not found
87+
}
88+
}
89+
}
90+
return0;
91+
}
92+
}
93+
}
94+
4195
}

‎src/test/java/com/fishercoder/_698Test.java

Lines changed: 54 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,12 +8,14 @@
88

99
publicclass_698Test {
1010
privatestatic_698.Solution1solution1;
11+
privatestatic_698.Solution2solution2;
1112
privatestaticint[]nums;
1213
privatestaticintk;
1314

1415
@BeforeClass
1516
publicstaticvoidsetup() {
1617
solution1 =new_698.Solution1();
18+
solution2 =new_698.Solution2();
1719
}
1820

1921
@Test
@@ -25,8 +27,59 @@ public void test1() {
2527

2628
@Test
2729
publicvoidtest2() {
28-
nums =newint[]{-1,1,0,0};
30+
nums =newint[]{-1,1,0,0};
2931
k =4;
3032
assertEquals(false,solution1.canPartitionKSubsets(nums,k));
3133
}
34+
35+
@Test
36+
publicvoidtest3() {
37+
nums =newint[]{4,3,2,3,5,2,1};
38+
k =4;
39+
assertEquals(true,solution2.canPartitionKSubsets(nums,k));
40+
}
41+
42+
@Test
43+
publicvoidtest4() {
44+
nums =newint[]{-1,1,0,0};
45+
k =4;
46+
assertEquals(false,solution2.canPartitionKSubsets(nums,k));
47+
}
48+
49+
@Test
50+
publicvoidtest5() {
51+
nums =newint[]{2,2,2,2,3,4,5};
52+
k =4;
53+
assertEquals(false,solution2.canPartitionKSubsets(nums,k));
54+
}
55+
56+
@Test
57+
publicvoidtest6() {
58+
nums =newint[]{1,2,3,4};
59+
k =3;
60+
assertEquals(false,solution2.canPartitionKSubsets(nums,k));
61+
}
62+
63+
@Test
64+
publicvoidtest7() {
65+
nums =newint[]{1,1,1,1,2,2,2,2};
66+
k =3;
67+
assertEquals(true,solution2.canPartitionKSubsets(nums,k));
68+
}
69+
70+
@Test
71+
publicvoidtest8() {
72+
/**This test case clearly shows how backtracking plays out beautifully!*/
73+
nums =newint[]{3522,181,521,515,304,123,2512,312,922,407,146,1932,4037,2646,3871,269};
74+
k =5;
75+
assertEquals(true,solution2.canPartitionKSubsets(nums,k));
76+
}
77+
78+
@Test
79+
publicvoidtest9() {
80+
nums =newint[]{1,2,3,5};
81+
k =2;
82+
assertEquals(false,solution2.canPartitionKSubsets(nums,k));
83+
}
84+
3285
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp