# Standard DFS Java Solution

• ``````public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result= new ArrayList<>();
dfs(nums,0,new ArrayList<Integer>(),result);
return result;
}

public void dfs(int[] nums,int index,List<Integer> path,List<List<Integer>> result){
for(int i=index;i<nums.length;i++){
if(i>index&&nums[i]==nums[i-1]) continue;
List<Integer> nPath= new ArrayList<>(path);
dfs(nums,i+1,nPath,result);
}
}
}``````

• Great hint!!

• Alternative solution modified from: https://leetcode.com/discuss/29631/java-subsets-solution/29631/java-subsets-solution

Only added one line: `if(i>index&&nums[i]==nums[i-1]) continue;`

``````public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();

if(nums.length == 0){
return result;
}

Arrays.sort(nums);
dfs(nums, 0, new ArrayList<Integer>(), result);
return result;
}

public void dfs(int[] nums, int index, List<Integer> path, List<List<Integer>> result){

for(int i = index; i < nums.length; i++){
if(i>index&&nums[i]==nums[i-1]) continue;
dfs(nums, i+1, path, result);
path.remove(path.size()-1);
}
}
``````

}

• @zn13621236 Much better than my recursive solution:

``````public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
if (nums == null || nums.length == 0) {
return Collections.<List<Integer>>emptyList();
}

Arrays.sort(nums);
Set<Integer> set = new HashSet<>();
List<List<Integer>> result = new ArrayList<>();
recurse(nums, 0, set, result);
return result;
}

private int recurse(int[] nums,
int index,
Set<Integer> set,
List<List<Integer>> result) {
// base case
if (index == nums.length) {
return 1;
}

// recursive case
int delta = recurse(nums, index + 1, set, result);
int finalSize = result.size();

if (set.contains(nums[index])) {
for (int i = finalSize - delta; i < finalSize; i ++) {
}
return delta;
}