Leetcode 90. subset II backtracking /medium

---

1.Description

Give you an array of integers nums , It may contain repeating elements , Please return all possible subsets of the array （ Power set ）.

Solution set You can't Contains a subset of repetitions . The solution set returned , Subsets can be classified by In any order array .

---

2.Example

 Input ：nums = [1,2,2]
 Output ：[[],[1],[1,2],[1,2,2],[2],[2,2]]

---

3.Solution

Using backtracking algorithm , Pay attention to whether the element to be added is the same as the previous element when recursing , Skip if the same , It should be that if there are the same elements in this layer, there will be repeated subsets in the next layer .

class Solution {
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
    
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        Arrays.sort(nums);
        backtrack(res,path,nums,0);
        return res;
    }
    
    public static void backtrack(List<List<Integer>> res,List<Integer> path,int[] nums,int index){
    
    	if(index > nums.length) {
    
    		return ;
    	}
    	res.add(new ArrayList<>(path));
    	for(int i=index;i<nums.length;i++) {
    
    		if(i!=index&&nums[i]==nums[i-1]) {
    
    			continue;
    		}
    		path.add(nums[i]);
    		backtrack(res, path, nums, i+1);
    		path.remove(path.size()-1);
    	}
    }
}