https://leetcode.com/problems/subsets-ii/

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10

给 元素重复 无序 数组，求所有的子数组，组合问题

package leetcode.problems.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SubsetsII {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(result, path, nums, 0);
        return result;
    }

    /**
     * 回溯法 选择可能性的N叉树，每个叉代表基于当前节点的一种选择可能性(数值一样的选择可能性视作同一种可能性要进行剪枝操作)
     * 怎么样写回溯算法(回溯法通用解题模板)
     * 1. 画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※: 状态变量start，用来标识当前的选择列表的起始位置。也就是标识每一层的状态
     * 2. 根据题意，确立结束条件: 因为每条路径都要加入结果集，所以是统计全路径。start越过数组边界的时候即是结束条件
     * 3. 找准选择列表(与函数参数相关),与第一步紧密关联※: 路径即子集
     * 4. 判断是否需要剪枝: 需要，因为存在同样的元素所以对于同一个节点往下分别选择一样的元素算同一种可能性
     * 5. 作出选择，递归调用，进入下一层
     * 6. 撤销选择 返回上一层
     * 参考：https://leetcode.cn/problems/subsets/solution/c-zong-jie-liao-hui-su-wen-ti-lei-xing-dai-ni-gao-/
     *
     * @param result 用来记录全部可能的路径的结果 list
     * @param path 从树的根节点开始往下走到全部叶子节点的路径
     * @param nums 题目给的集合
     * @param start 当前节点起始下标
     */
    private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, int start) {
        result.add(new ArrayList<>(path)); // 记得要深拷贝不然传引用的话result list里面全是存的同一个path list的地址
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i-1] == nums[i]) { // 剪枝: 同样的数字不必再进入子树了
                continue;
            }
            path.add(nums[i]);
            backtrack(result, path, nums, i+1);
            path.remove(path.size()-1);
        }
    }

    public List<List<Integer>> subsetsWithDup2(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                List<Integer> subset = new ArrayList<>();
                for (int index = i; index <= j; index++) {
                    subset.add(nums[index]);
                }
                result.add(subset);
            }
        }
        return result;
    }

    public static void print(List<List<Integer>> subsets) {
        for (List<Integer> subset : subsets) {
            System.out.print("[");
            for (int i = 0; i < subset.size(); i++) {
                System.out.print(subset.get(i));
                if (i != subset.size()-1)
                    System.out.print(",");
            }
            System.out.println("]");
        }
    }
}