Permutations

Given a collection of distinct numbers, 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]
]

Algorithm:

See Combinations. Simply without rule 2. But the IO settings is a little bit different than Combination, which give you n numbers from 1~n and k buckets. In this problem, it gives you a set of predefined numbers. So instead of start with the first number, you start with nums[0]. And you need an additional array to mark the numbers that already show up.

Solution:

class Solution {
  
    void DFS(int[] visited, int[] nums, List<Integer> ans, List<List<Integer>> res)
    {
      if( ans.size() == nums.length ){
        List<Integer> tmp = new ArrayList<Integer>(ans);
        res.add(tmp);
        return;
      }
      for(int i = 0; i < nums.length; i++){
        if( visited[i] == 0 ){
          visited[i] = 1;
          ans.add(nums[i]);
          DFS(visited, nums, ans, res);
          ans.remove(ans.size()-1);
          visited[i] = 0;
        }
      }
    }
    
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> answer = new ArrayList<Integer>();
        int[] visited = new int[nums.length]; 
        
        DFS(visited, nums, answer, result);
      
        return result;
    }
}