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

Commit31da148

Browse files
committed
078 (3) add iterative solution
1 parent25c2f1e commit31da148

File tree

3 files changed

+180
-16
lines changed

3 files changed

+180
-16
lines changed

‎src/_078_Subsets/Solution.java

Lines changed: 33 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -26,27 +26,44 @@
2626
/** see test {@link _078_Subsets.SolutionTest } */
2727
publicclassSolution {
2828

29+
// try to insert each number into all existing subsets
2930
publicList<List<Integer>>subsets(int[]nums) {
30-
List<List<Integer>>result =newArrayList<List<Integer>>();
31-
List<Integer>list =newArrayList<>();
32-
intpos =0;
33-
// sort because it is required to put elements in non-descending order
31+
List<List<Integer>>res =newArrayList<List<Integer>>();
3432
Arrays.sort(nums);
35-
subsetsHelper(nums,pos,list,result);
36-
returnresult;
33+
34+
// push initial empty subset
35+
res.add(newArrayList<>());
36+
37+
for (intnum :nums) {
38+
intsz =res.size();// we don't need temp list any more
39+
for (inti =0;i <sz;i++) {
40+
List<Integer>list =newArrayList<>(res.get(i));
41+
list.add(num);
42+
res.add(list);
43+
}
44+
}
45+
returnres;
3746
}
47+
48+
// we have to use temporary list
49+
publicList<List<Integer>>subsets2(int[]nums) {
50+
List<List<Integer>>res =newArrayList<List<Integer>>();
51+
Arrays.sort(nums);
52+
53+
// push initial empty subset
54+
res.add(newArrayList<>());
3855

39-
privatevoidsubsetsHelper(int[]nums,intpos,List<Integer>list,
40-
List<List<Integer>>result) {
41-
// ! not result.add(list)
42-
result.add(newArrayList<>(list));
43-
for (inti =pos;i <nums.length;i++) {
44-
list.add(nums[i]);
45-
// ! not (pos + 1)
46-
subsetsHelper(nums,i +1,list,result);
47-
list.remove(list.size() -1);
56+
for (intnum :nums) {
57+
// try insert num into all existing subsets
58+
List<List<Integer>>temp =newArrayList<>();
59+
for (List<Integer>sub :res) {
60+
List<Integer>list =newArrayList<>(sub);
61+
list.add(num);
62+
temp.add(list);
63+
}
64+
res.addAll(temp);
4865
}
49-
66+
returnres;
5067
}
5168

5269
}
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
/**
2+
* Time : O(2^n); Space: O()
3+
* @tag : Array; Backtracking; Bit Manipulation
4+
* @by : Steven Cooks
5+
* @date: Jun 7, 2015
6+
*************************************************************************
7+
* Description:
8+
*
9+
* My Submissions Question Solution
10+
* Given a set of distinct integers, nums, return all possible subsets.
11+
*
12+
* Note: Elements in a subset must be in non-descending order.
13+
* The solution set must not contain duplicate subsets.
14+
* For example, If nums = [1,2,3], a solution is:
15+
* [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
16+
*
17+
*************************************************************************
18+
* {@link https://leetcode.com/problems/subsets/ }
19+
*/
20+
package_078_Subsets;
21+
22+
importjava.util.ArrayList;
23+
importjava.util.Arrays;
24+
importjava.util.List;
25+
26+
/** see test {@link _078_Subsets.SolutionTest } */
27+
publicclassSolutionRecursive {
28+
29+
publicList<List<Integer>>subsets(int[]nums) {
30+
List<List<Integer>>result =newArrayList<List<Integer>>();
31+
List<Integer>list =newArrayList<>();
32+
intpos =0;
33+
// sort because it is required to put elements in non-descending order
34+
Arrays.sort(nums);
35+
subsetsHelper(nums,pos,list,result);
36+
returnresult;
37+
}
38+
39+
privatevoidsubsetsHelper(int[]nums,intpos,List<Integer>list,
40+
List<List<Integer>>result) {
41+
// ! not result.add(list)
42+
result.add(newArrayList<>(list));
43+
for (inti =pos;i <nums.length;i++) {
44+
list.add(nums[i]);
45+
// ! not (pos + 1)
46+
subsetsHelper(nums,i +1,list,result);
47+
list.remove(list.size() -1);
48+
}
49+
}
50+
51+
}
Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
package_078_Subsets;
2+
3+
importstaticcom.leetcode.Test.*;
4+
5+
importjava.util.ArrayList;
6+
importjava.util.Arrays;
7+
importjava.util.List;
8+
9+
importorg.junit.After;
10+
importorg.junit.Before;
11+
importorg.junit.Rule;
12+
importorg.junit.Test;
13+
importorg.junit.rules.Timeout;
14+
15+
publicclassSolutionRecursiveTest {
16+
17+
/** Test method for {@link _078_Subsets.SolutionRecursive } */
18+
SolutionRecursivesolution;
19+
20+
@Rule
21+
publicTimeoutglobalTimeout =newTimeout(500);
22+
23+
@Before
24+
publicvoidsetUp()throwsException {
25+
solution =newSolutionRecursive();
26+
}
27+
28+
@After
29+
publicvoidtearDown()throwsException {
30+
solution =null;
31+
}
32+
33+
@Test
34+
publicvoidTest1() {
35+
int[]nums = {1,2,3 };
36+
List<List<Integer>>actuals =solution.subsets(nums);
37+
List<List<Integer>>expecteds =newArrayList<>();
38+
expecteds.add(Arrays.asList());
39+
expecteds.add(Arrays.asList(1));
40+
expecteds.add(Arrays.asList(2));
41+
expecteds.add(Arrays.asList(3));
42+
expecteds.add(Arrays.asList(1,3));
43+
expecteds.add(Arrays.asList(1,2));
44+
expecteds.add(Arrays.asList(2,3));
45+
expecteds.add(Arrays.asList(1,2,3));
46+
assertEqualsIgnoreOrder(expecteds,actuals);
47+
}
48+
49+
@Test
50+
publicvoidTest2() {
51+
int[]nums = {1,2 };
52+
List<List<Integer>>actual =solution.subsets(nums);
53+
List<List<Integer>>expecteds =newArrayList<>();
54+
expecteds.add(Arrays.asList());
55+
expecteds.add(Arrays.asList(1));
56+
expecteds.add(Arrays.asList(2));
57+
expecteds.add(Arrays.asList(1,2));
58+
assertEqualsIgnoreOrder(expecteds,actual);
59+
}
60+
61+
@Test
62+
publicvoidTest3() {
63+
int[]nums = {1 };
64+
List<List<Integer>>actual =solution.subsets(nums);
65+
List<List<Integer>>expecteds =newArrayList<>();
66+
expecteds.add(Arrays.asList());
67+
expecteds.add(Arrays.asList(1));
68+
assertEqualsIgnoreOrder(expecteds,actual);
69+
}
70+
71+
@Test
72+
publicvoidTest4() {
73+
int[]nums = {4,1,0 };
74+
List<List<Integer>>actual =solution.subsets(nums);
75+
List<List<Integer>>expecteds =newArrayList<>();
76+
expecteds.add(Arrays.asList());
77+
expecteds.add(Arrays.asList(0));
78+
expecteds.add(Arrays.asList(0,1));
79+
expecteds.add(Arrays.asList(0,4));
80+
expecteds.add(Arrays.asList(0,1,4));
81+
expecteds.add(Arrays.asList(1));
82+
expecteds.add(Arrays.asList(1,4));
83+
expecteds.add(Arrays.asList(4));
84+
assertEqualsIgnoreOrder(expecteds,actual);
85+
}
86+
87+
@Test
88+
publicvoidTest5() {
89+
int[]nums = { };
90+
List<List<Integer>>actual =solution.subsets(nums);
91+
List<List<Integer>>expecteds =newArrayList<>();
92+
expecteds.add(Arrays.asList());
93+
assertEqualsIgnoreOrder(expecteds,actual);
94+
}
95+
96+
}

0 commit comments

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