# Subsets

## Problem

Given a list of numbers that may has duplicate numbers, return all possible subsets

## Example

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

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

## Note

Each element in a subset must be in non-descending order. The ordering between two subsets is free. The solution set must not contain duplicate subsets.

## Challenge

Can you do it in both recursively and iteratively?

## Key Point

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

## Code - Java

class Solution {
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
public ArrayList<ArrayList<Integer>> subsetsWithDup(ArrayList<Integer> S) {
Set<ArrayList<Integer>> result = new HashSet<ArrayList<Integer>>();

Collections.sort(S);
int size = S.size();

for (int i = 0; i < size; i++) {
Set<ArrayList<Integer>> newResult = new HashSet<>(result);
for (ArrayList<Integer> list : result) {
ArrayList<Integer> newList = new ArrayList<Integer>(list);
}
result = newResult;
}
ArrayList<ArrayList<Integer>> finalResult = new ArrayList<ArrayList<Integer>>(result);

return finalResult;
}
}

public class Solution {

private List<List<Integer>> assemble(int[] S, int n, boolean included) {
if (n == S.length - 1) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (included) {
return result;
} else {
List<Integer> list = new ArrayList<Integer>();
return result;
}
}

List<List<Integer>> result = new ArrayList<List<Integer>>();
for (List<Integer> l : assemble(S, n + 1, true)) {
List<Integer> list = new ArrayList<Integer>();
if (included) {
}
}
for (List<Integer> l : assemble(S, n + 1, false)) {
List<Integer> list = new ArrayList<Integer>();
if (included) {
}
}
return result;
}

public List<List<Integer>> subsets(int[] S) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
}