46. Permutations - Medium

前往題目

想法

• 之前做過的簡單backtracking

思路

1. backtracking
2. check是否數字已存在，以免重複加入

暫存的list可能可以用其他實作方式，可以removeLast in O(1)，不然arraylist要移除最後一項需要N次操作

Code

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        res = new ArrayList<List<Integer>>();

        backtrack(nums, new ArrayList<>());

        return res;
    }

    private void backtrack(int[] nums, List<Integer> comb) {
        if (comb.size() == nums.length) {
            res.add(new ArrayList<Integer>(comb));
            return;
        }

        for (int i = 0; i < nums.length; ++i) {
            if (comb.contains(nums[i])) 
                continue;
            comb.add(nums[i]);
            backtrack(nums, comb);
            comb.remove(comb.size() - 1);
        }
    }
}