78. Subsets - Medium

前往題目

之前寫過了，這次一看到就知道要用backtracking但是細節漏了一點

想法

• 用backtracking

思路

1. 每次疊代加入當前array到答案裡
2. 並且用下一個num繼續呼叫backtrack
3. 循環結束前把最後一位去掉

傳i + 1的原因是讓演算法不要取到同一個數字

Code

class Solution {
    List<List<Integer>> res;
    
    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<List<Integer>>();
        backtrack(nums, new ArrayList<>(), 0);
        return res;
    }

    private void backtrack(int[] nums, List<Integer> element, int start) {
        // Add the possible list
        res.add(new ArrayList<Integer>(element));

        for (int i = start; i < nums.length; ++i) {
            element.add(nums[i]);
            backtrack(nums, element, i + 1);
            // Eject
            element.remove(element.size() - 1);
        }
    }
}

2024/03/10

• 有寫出來，一個小bug，應該要是i的地方寫成index造成無限迴圈