class Solution {

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        result = new ArrayList<>();

        List<Integer> ans = new ArrayList<Integer>();

        Arrays.sort(nums); //nums可能是乱序的，要先排序

        backtrack(ans, nums, 0);

        return result;

    }

    public void backtrack(List<Integer> ans, int[] nums, int depth){

        if(depth >= nums.length) {

            List<Integer> new_ans = new ArrayList<Integer>(ans);

            result.add(new_ans);

            return;

        }

        int i = depth+1;

        while(i < nums.length){

            if(nums[depth] == nums[i]) i++;

            else break;

        }

        int j = depth;

        backtrack(ans, nums, i); //not add

        while(j < i){

            ans.add(nums[depth]);

            backtrack(ans, nums, i);

            j++;

        }

        //reset

        while(j > depth){

            ans.remove(ans.size()-1);

            j--;

        }

    }

    private List<List<Integer>> result;

}