Leetcode90:子集II（回溯算法）

Leetcode90:子集II

• 题目：

  • 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

    解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

• 思路：回溯算法（去重：同一树层中使用过的、相同的元素）
• 代码如下：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup( int[] nums ) {
        Arrays.sort( nums );
        backTrack( nums, 0 );
        return res;
    }
    void backTrack( int[] nums, int startIndex ){
        res.add( new ArrayList<>(path) );
        for ( int i = startIndex; i < nums.length; i++ ){
            //跳过当前树层使用过的、相同的元素
            if ( i > startIndex && nums[i-1] == nums[i] ){
                continue;
            }
            path.add( nums[i] );
            backTrack( nums, i + 1 );
            path.removeLast();
        }
    }
}