78. 子集

LeetCode： 78. 子集

回溯。

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        ans.add(new ArrayList<>(temp));
        if(nums == null || nums.length == 0){ return ans; }
        int len = nums.length;

        getRes(nums,0, len);

        return  ans;
    }

    public void getRes(int [] arr, int start, int len){
        for (int i = start; i < len; i++) {
                // 沒被存取過
                temp.add(arr[i]);
                // 新增一種組合
                ans.add(new ArrayList<>(temp));
                getRes(arr, i + 1, len);
                temp.remove(temp.size() - 1);
        }

        return ;
    }
}

---

根據大佬的思路
挺有意思的

    /**
     *  遇到一個數，加入子集，然後把該數加入到子集中形成新的子集
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets2(int[] nums) {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        if(nums == null || nums.length == 0){ ans.add(list);return ans; }
        for (int i = 0; i < nums.length; i++) {
            // 遇到一個數
            list.add(nums[i]);
            // 子集
            ans.add(new ArrayList<>(list));

            int len = ans.size() - 1;
            // 遍歷子集，與新增的數形成新的子集
            for (int j = 0; j < len; j++) {
                list.addAll(ans.get(j));
                // 新增一種組合
                ans.add(new ArrayList<>(list));

                list.clear(); list.add(nums[i]);
            }
            list.clear();
        }

        ans.add(new ArrayList<>());
        return ans;
    }