## Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]

Output:

[

[3],

[1],

[2],

[1,2,3],

[1,3],

[2,3],

[1,2],

[]

]

[Leetcode 78 Subsets] (https://leetcode.com/problems/subsets/)

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class Solution {
Set<Set<Integer>> m_sum;
Solution() {
m_sum = new HashSet<Set<Integer>>();
}
Set<Integer> makeDeepCopyInteger(Set<Integer> old){
Set<Integer> copy = new HashSet<Integer>(old.size());
Iterator<Integer> it = old.iterator();
while (it.hasNext()) {
copy.add(it.next());
}
return copy;
}
void find_subset(Set<Integer> currentList, int[] nums) {
// System.out.println(currentList);
for (int i = 0; i < nums.length; i++) {
if (! currentList.contains(nums[i])) {
currentList.add(nums[i]);
if (! m_sum.contains(currentList)) {
m_sum.add(makeDeepCopyInteger(currentList));
find_subset(currentList, nums);
}
currentList.remove(nums[i]);
}
}
}
public List<List<Integer>> subsets(int[] nums) {
List<Integer> lst = new ArrayList<Integer>();
Set<Integer> myLst = new HashSet<Integer>();
m_sum.add(new HashSet<Integer>());
find_subset(myLst, nums);
List<List<Integer>> rLst = new ArrayList<List<Integer>>();
Iterator<Set<Integer>> i = m_sum.iterator();
while(i.hasNext()) {
List<Integer> temp = new ArrayList<Integer>();
Iterator<Integer> j = i.next().iterator();
while(j.hasNext()) {
temp.add(j.next());
}
rLst.add(temp);
}
return rLst;
}
}

## Subset Sum Algorithm

Explanation

The subset sum algorithm is one of the simpler implementations of backtracking. The problem takes in a list and a value, and outputs different subsets from the list that sum up to the value. The implementation below is done in Java.

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SubsetSum {
List<Integer> makeDeepCopyInteger(List<Integer> old){
ArrayList<Integer> copy = new ArrayList<Integer>(old.size());
for(Integer i : old){
copy.add(new Integer(i));
}
return copy;
}
List<List<Integer>> subset_sum(Integer current, Integer currentIndex, Integer goal, List<Integer> currentPath, List<List<Integer>> ans, List<Integer> lst, List<Integer> lstused) {
if (current == goal) {
ans.add(makeDeepCopyInteger(currentPath));
return ans;
}
else {
for (int i = currentIndex + 1; i < lst.size(); i++) {
if (current + lst.get(i) <= goal && lstused.get(i) == 0) {
lstused.set(i, 1);
currentPath.add(lst.get(i));
ans = subset_sum(current + lst.get(i), i, goal, currentPath, ans, lst, lstused);
currentPath.remove(currentPath.size() - 1);
lstused.set(i, 0);
}
}
return ans;
}
}
public static void main (String args[]) {
SubsetSum subsetSum = new SubsetSum();
List<Integer> lst = new ArrayList<Integer>(Arrays.asList(10, 7, 5, 18, 12, 20, 15));
List<Integer> lst2 = new ArrayList<Integer>();
for (int i = 0; i < lst.size(); i++) {
lst2.add(0);
}
List<Integer> currentPath = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
subsetSum.subset_sum(0, -1, 35, currentPath, ans, lst, lst2);
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans.get(i).size(); j++) {
System.out.print(ans.get(i).get(j));
System.out.print(" ");
}
System.out.println();
}
}
}