算法題之求子集問題

題目描述

給定一組不含重複元素的整數數組 nums，傳回該數組所有可能的子集（幂集）。

輸入: nums = [1,2,3] 輸出:

[

[3],

[1],

[2],

[1,2,3],

[1,3],

[2,3],

[1,2],

[]

]

題解

代碼實作

package com.bingym.algorithm.recursionproblems.subset;

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

public class FindAllSubset {
    /*
    * 思路:
    * 利用遞歸回溯的方法:
    * 當子集的長度大于start起始位置時,退出遞歸
    * 否則将該子集加入到list集合中
    * 并進行遞歸調用
    * 在每一次遞歸回溯時,将子集中的最後一個元素剔除
    * */
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        FindAllSubset subset = new FindAllSubset();
        List<List<Integer>> subsets = subset.subsets(nums);
        for (List<Integer> list : subsets) {
            System.out.println(list);
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        //建立一個list集合儲存最終的子集集合
        List<List<Integer>> list = new ArrayList<>();
        //定義一個集合,儲存每一種子集
        List<Integer> numList = new ArrayList<>();
        //求出數組的長度
        int len = nums.length;
        //從數組的第一個位置開始進行子集的求解
        findSubset(0,len,nums,numList,list);
        return list;
    }

    private void findSubset(int start,int len, int[] nums, List<Integer> numList, List<List<Integer>> list) {
        //如果目前子集集合的長度大于所起始的位置,則傳回
        if (numList.size()  > start) {
            return;
        }
        //否則,将此子集加入list中
        list.add(new ArrayList<>(numList));
        //for循環進行子集的添加
        for (int i = start; i < len; i++) {
            numList.add(nums[i]);
            //遞歸
            findSubset(i + 1,len,nums,numList,list);
            //當傳回時,去掉目前子集集合的最後一個元素
            numList.remove(numList.size() - 1);
        }
    }
}