[Link] https://leetcode.com/problems/combination-sum-ii/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> list = new LinkedList<>();
HashMap<Integer, Integer> hm = new HashMap<>();
for(int e: candidates){
if(hm.containsKey(e)) hm.put(e, hm.get(e) + 1);
else hm.put(e, 1);
}
List<HashMap.Entry<Integer, Integer>> entries = new ArrayList<>(hm.entrySet());
dfs(list, new ArrayList<Integer>(), entries, 0, target);
return list;
}
public void dfs(List<List<Integer>> list, List<Integer> templist, List<HashMap.Entry<Integer, Integer>> entries, int idx, int left) {
if(left == 0) {
list.add(new ArrayList<>(templist));
return;
}
for(int i = idx; i < entries.size(); i++) {
Map.Entry<Integer, Integer> entry = entries.get(i);
int val = entry.getKey();
if(val <= left) {
int loop = Math.min(left / val, entry.getValue());
for(int j = 0; j < loop; j++) {
templist.add(val);
left -= val;
dfs(list, templist, entries, i + 1, left);
}
for(int j = 0; j < loop; j++) templist.remove(templist.size() - 1);
left += val * loop;
} else continue;
}
}
static <T> void print(T s) { System.out.print(s); }
static <T> void println(T s) { System.out.println(s); }
}
Without HashMap(ArrayList + Array)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
ArrayList<Integer> al = new ArrayList<>();
List<List<Integer>> list = new LinkedList<List<Integer>>();
int[] cnt = new int[51];
int tmp = 0;
Arrays.sort(candidates);
for(int e: candidates){
if(tmp != e) {
tmp = e;
al.add(tmp);
}
cnt[tmp]++;
}
dfs(list, new ArrayList<Integer>(), al, cnt, 0, target);
return list;
}
public void dfs(List<List<Integer>> list, List<Integer> templist, ArrayList<Integer> al, int[] cnt, int idx, int left) {
if(left == 0) {
list.add(new ArrayList<>(templist));
return;
}
for(int i = idx; i < al.size(); i++) {
int val = al.get(i);
if(val <= left) {
int loop = Math.min(left / val, cnt[val]);
for(int j = 0; j < loop; j++) {
templist.add(val);
left -= val;
dfs(list, templist, al, cnt, i + 1, left);
}
for(int j = 0; j < loop; j++) templist.remove(templist.size() - 1);
left += val * loop;
} else return;
}
}
}