046.Permutations

Posted on | In

Solution 1: accepted 7ms

DFS, similar to question 078. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<>();
        permuteHelper(result, list, nums);
        return result;
    }
    
    public void permuteHelper(List<List<Integer>> result, List<Integer> list, int[] nums) {
        if (nums.length == list.size()) {
            result.add(new ArrayList<Integer>(list));  // use "else" or "return" after it to end the recursion
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (!list.contains(nums[i])) {
                    list.add(nums[i]);
                    permuteHelper(result, list, nums);
                    list.remove(list.size() - 1);
                }
            }
        }
    }
}