46. Permutations

Given a collection ofdistinctnumbers, return all possible permutations.

For example,
[1,2,3]have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Analysis:

DFS, to loop through remaining elements in array at each level, use swap() to try different element at each level without losing elements in the next level. (Can also use a set<Integer> to do it)

Base case: tempSolutionList.size() == nums.length;

Complexity:

Time: O(N!)

Space: O(N)

Code:

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> returnList = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0){
            return returnList;
        }

        dfs(new ArrayList<Integer>(), nums, returnList, 0);
        return returnList;
    }

    private void dfs(List<Integer> tempList, int[] nums, List<List<Integer>> returnList, int pos){
        if(tempList.size() == nums.length){
            returnList.add(new ArrayList<Integer>(tempList));
            return;
        }

        for(int i = pos; i < nums.length; i++){
            swap(pos, i, nums);
            tempList.add(nums[pos]);
            dfs(tempList, nums, returnList, pos+1);
            tempList.remove(tempList.size()-1);
            swap(pos, i, nums);
        }
    }

    private void swap(int a, int b, int[] nums){
        if(a != b){
            int temp = nums[a];
            nums[a] = nums[b];
            nums[b] = temp;
        }
    }
}