## Given problem

Given a set of distinct integers, S, return all possible subsets.

Belows are some constraints of this problem:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.
• Also, the subsets should be sorted in ascending ( lexicographic ) order.
• The list is not necessarily sorted.

For example:

``````If S = [1,2,3], a solution is:

[
[],
[1],
[1, 2],
[1, 2, 3],
[1, 3],
[2],
[2, 3],
[3],
]
``````

## Using iterative version

``````public static List<List<Integer>> subsetIII(int[] nums) {
List<List<Integer>> res = new ArrayList<>();

for (int value : nums) {
List<List<Integer>> subSets = new ArrayList<>(res);

for (List<Integer> tmp : res) {
}

for (List<Integer> tmp : subSets) {
}
}

return res;
}
``````

The complexity of this problem:

• Time complexity: O(n * 2^n)
• Space complexity: O(n * 2^n)

## Using backtracking

1. Using index is greater or equal than the array’s length to terminate backtracking

`````` public static void main(String[] args) {
int[] nums = {1, 2, 3};
List<List<Integer>> res = subset(nums);
res.stream().forEach(values -> {
System.out.print("[");
values.stream().forEach(value -> System.out.print(value + ", "));
System.out.print("]");
System.out.println();
});
}

public static List<List<Integer>> subset(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
subset(nums, res, new ArrayList<>(), 0);
return res;
}

private static void subset(int[] nums, List<List<Integer>> res, List<Integer> values, int index) {

for (int i = index; i < nums.length; ++i) {
subset(nums, res, values, i + 1);
values.remove(values.size() - 1);
}
}
``````
2. Using the size of subarrays to iterate all cases

`````` public static List<List<Integer>> subset(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
for (int sizeSub = 0; sizeSub <= nums.length; ++sizeSub) {
subsetII(nums, res, new ArrayList<>(), 0, sizeSub);
}

return res;
}

public static void subset(int[] nums, List<List<Integer>> res, List<Integer> values, int index, int k) {
if (values.size() == k) {
return;
}

for (int i = index; i < nums.length; ++i) {
subsetII(nums, res, values, i + 1, k);
values.remove(values.size() - 1);
}
}
``````

The complexity of this problem:

• Time complexity: O(n * 2^n)
• Space complexity: O(n * 2^n)

## Wrapping up

• The background of backtracking algorithm about listing all cases of a problem.
• There are an array - currentArr to contain the result of the current operations, and an array - finalArr to contain all final results.
• The specific condition to put currentArr to finalArr.
• If the current operation finished, the currentArr will get out of the current result to come back the previous results. Then, continue with the next operations.

Refer:

https://www.interviewbit.com/problems/subset/