My idea was to start out with an empty subset and either take or don't take the next element in the input array. Here's how it goes down for input `[1,2,3]`

:

start with

```
[] // empty set is always a subset
```

then either take or not take the next element (`1`

), this doubles the result size:

```
[] // not take 1
[1] // take 1 + new
```

then take or not take the next element: `2`

```
[] // not take 1, not take 2
[2] // not take 1, take 2 + new
[1] // take 1, not take 2
[1,2] // take 1, take 2 + new
```

and finally take or not take `3`

.

```
[] // not take 1, not take 2, not take 3
[3] // not take 1, not take 2, take 3 + new
[2] // not take 1, take 2, not take 3
[2,3] // not take 1, take 2, take 3 + new
[1] // take 1, not take 2, not take 3
[1,3] // take 1, not take 2, take 3 + new
[1,2] // take 1, take 2, not take 3
[1,2,3] // take 1, take 2, take 3 + new
```

And we're done, we have all `2^3 = 8`

subsets generated.

It is possible to generate these with a simple loop, there's only one trick here, the variable `size`

. It's usually a good practice to cache method call results, but now it is cached for a different reason: because it changes in every iteration. If we don't want to end up with an infinite loop, we have to remember how many `results`

were available in the previous iteration, which is exactly the `size()`

of the `result`

at the beginning of the current iteration.

```
public List<List<Integer>> subsets(int[] nums) {
Arrays.sort(nums); // make sure subsets are ordered
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>()); // start with empty set
for (int i = 0; i < nums.length; ++i) {
for (int j = 0, size = result.size(); j < size; ++j) { // remember
List<Integer> subset = new ArrayList<>(result.get(j)); // copy a new one
subset.add(nums[i]); // expand
result.add(subset); // collect
}
}
return result;
}
```

It is also necessary to order the input to satisfy the requirement:

- Elements in a subset must be in non-descending order.

Because `i`

is increasing it means that whatever we take from nums will also be in increasing order.

The other requirement:

- The solution set must not contain duplicate subsets.

is automatically guaranteed by the input specification and the algorithm walking indices straight and once:

Given a set of

distinctintegers,`nums`

, return all possible subsets.[emphasis mine]