（回溯法）LeetCode#90. Subsets II

• 题目：给定一个二维nums，数组中包含重复元素，返回所有子集(不能包括重复的子集)
• 难度：Medium
• 思路：遍历数组得到所有子集是一个回溯的思想，由于数组中有重复元素，然而子集又不能出现重复，所以需要在回溯方法中额外加入一个标志数组boolean[] flag

  如果flag[i-1]为FALSE并且nums[i]等于nums[i-1],那么说明这次回溯nums[i]应该被过滤
             

• 代码：

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null || nums.length == ){
            return result;
        }
        Arrays.sort(nums);
        result.add(new ArrayList<Integer>());
        backtrack(result, new ArrayList<Integer>(), , nums, new boolean[nums.length]);
        return result;
    }
    public void backtrack(List<List<Integer>> list, List<Integer> tmp, int start, int[] nums, boolean[] flag) {
        for(int i = start; i < nums.length; i++) {
            if(i >  && nums[i] == nums[i-] && flag[i-] == false) {
                continue;
            }
            tmp.add(nums[i]);
            list.add(new ArrayList<>(tmp));
            flag[i] = true;
            backtrack(list, tmp, i+, nums, flag);
            tmp.remove(tmp.size()-);
            flag[i] = false;
        }
    }
}
           

Subsets

http://blog.csdn.net/u012559634/article/details/71915687