LeetCode 46. Permutations

Question

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

https://leetcode.com/problems/permutations/

• Solution1

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> res = new ArrayList<>();
   // Arrays.sort(nums); // not necessary
   backtrack(res, new ArrayList<>(), nums);
   return res;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      for(int i = 0; i < nums.length; i++){ 
         if(tempList.contains(nums[i])) continue; // element already exists, skip
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
} 
/*
    Time: O(N!),T(n) = n( c1 + T(n-1) )
    Space: O(N)
*/

Complexity:

Time complexity: O(N!)

Space complexity: O(n)