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();
        }
    }
}