LeetCode_回溯_中等_78.子集

目錄

• 1.題目
• 2.思路
• 3.代碼實作（Java）

1.題目

給你一個整數數組 nums ，數組中的元素 互不相同 。傳回該數組所有可能的子集（幂集）。

解集不能包含重複的子集。你可以按任意順序傳回解集。

示例 1：

輸入：nums = [1,2,3]

輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

輸入：nums = [0]

輸出：[[],[0]]

提示：

1 <= nums.length <= 10

-10 <= nums[i] <= 10

nums 中的所有元素 互不相同

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/subsets

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2.思路

（1）回溯

經過分析可知，本題可以看作是在LeetCode77.組合這題的基礎上，針對組合中的整數個數 k 進行一次0~nums.length的循環，因為本題中子集元素的個數就相當于那題一個組合中元素的個數，是以隻需将那題中的回溯代碼稍加修改即可。

3.代碼實作（Java）

//（1）回溯
class Solution {

    List<List<Integer>> res = new ArrayList<List<Integer>>();
    LinkedList<Integer> path = new  LinkedList<Integer>();

    public List<List<Integer>> subsets(int[] nums) {
        int length = nums.length;
        for(int i=0;i<=length;i++){
            backTrack(0,length,i,nums);
        }
        //res.add(Arrays.asList(nums));
        return res;
    }

    public void backTrack(int index, int length, int k,int[] nums){
        //存放符合條件的結果
        if(path.size()==k){
            res.add(new ArrayList<Integer>(path));
            return;
        }
        /*
            循環限制條件i<=n-(k-path.size())+1的目的是剪枝優化
            i:目前選擇的整數在[1,n]中的位置，同時也是被選擇的整數本身
            path.size():已經選擇的整數個數
            k-path.size():待選擇的元素個數
            n-(k-path.size())+1:在nums[0...length-1]中至少要開始周遊的位置(包括起始位置，是以要+1)，否則将不能得到k個數的組合
        */
        for(int i=index;i<length-(k-path.size())+1;i++){
            //将目前節點加入到path中
            path.add(nums[i]);
            //下一層搜尋從i+1開始
            backTrack(i+1,length,k,nums);
            //删除并傳回最後一個元素
            path.removeLast();
        }
    }
}