去重的前提就先排序。对于这个思想我不太好理解，转不过来弯。 下面是我的题解：

  /**
 * 90. 子集 II
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 * <p>
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 *
 * hint 去重一定要排序
 */
public class Solution90 {
    static int offset = 10;

    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        Arrays.sort(nums);
        combination(nums, nums.length, 0, path, ans);
        ans.add(new ArrayList<Integer>());
        return ans;
    }

    private static void combination(int[] nums, int len, int start, Deque<Integer> path, List<List<Integer>> ans) {
        if (path.size() == len)
            return;
        boolean[] used = new boolean[20];

        for (int i = start; i < len; i++) {
            int num = nums[i];
            if (used[num + offset])
                continue;

            used[num + offset] = true;
            path.addLast(num);
            ans.add(new ArrayList<>(path));
            combination(nums, len, i + 1, path, ans);
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        int[] nums = {4, 4, 1, 4};
        System.out.println(subsetsWithDup(nums));
        
    }
}

这个题解是对的。但是我第一遍写的时候，并没有Arrays.sort(candidates);排序。结果就是错的。对于这道题的思想。我能明白。但是对于不排序就是错的我很不能理解。其实我们要做的就是对树形结构，同一层不能出现重复元素，出现只取一次。思想我也理解。我甚至都能画出两个树形结构的不同：
但是我就是想不通为什么122 排序后就正确，212不排序就不正确。按道理来说树的每层循环，同一层级used这个数组已经保证了不存在重复元素，同时i+1保证之前的元素不参与后续的结果。为什么非要排序才是正确的。

Ps：对于 39号问题和40号问题排序我能理解
39号

/**
 * 39. 组合总和
 * <p>
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
 * 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * <p>
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * <p>
 * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
 * {@link Solution39}
 */
public class Solution39 {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<List<Integer>> ans = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        Arrays.sort(candidates);
        combination(candidates, candidates.length, 0, path, ans, target, 0);

        return ans;
    }

    private static void combination(int[] nums, int len, int start, LinkedList<Integer> path, List<List<Integer>> ans, int target, int sum) {
        if (sum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < len && nums[i] <= target; i++) {
            if (sum + nums[i] > target)
                break;
            sum = sum + nums[i];
            path.addLast(nums[i]);
            combination(nums, len, i, path, ans, target, sum);
            path.removeLast();
            sum = sum - nums[i];
        }
    }


    public static void main(String[] args) {
        int[] nums = {2, 3, 6, 7};
        System.out.println(combinationSum(nums, 7));
    }
}

40号：

/**
 * 40. 组合总和 II
 * <p>
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 * <p>
 * 注意：解集不能包含重复的组合。
 */
public class Solution40 {

    /**
     * 思路
     * 回溯法
     * 需要注意的是 这里存在重复元素
     * 在同一层遍历中 相同元素的结果是一样 所以不用
     * <p>
     * <p>
     * 1。 同一层元素 重复的不用在查找
     * 2 路径上 用过的数字不能再用
     */
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();

        Arrays.sort(candidates);
        combination(candidates, candidates.length, 0, target, path, ans);
        return ans;
    }

    private static void combination(int[] nums, int len, int start, int target, LinkedList<Integer> path, List<List<Integer>> ans) {
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }

        boolean[] used = new boolean[100];
        for (int i = start; i < len && nums[i] <= target; i++) {
            int num = nums[i];
            if (target - num < 0)
                break;
            if (used[num])
                continue;
            used[num] = true;
            path.addLast(num);
            combination(nums, len, i + 1, target - num, path, ans);
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        int[] nums={2,5,2,1,2};
        System.out.println(combinationSum2(nums,5));
    }
}

这两道题都是完全自己做出来，排序也是自己想出来，原因是剪枝。只有排序后两题中的nums[i] <= target 才能成立。使得同一层中单个大于target，升序后，后面的数一定全部大于target。很有必要。但90号题 我怎么都绕不过来。leetcode的题解看了好多，都是强调结果。去重就要排序。但我不想死记硬背。希望老师能指点一下。