Permutation I

Given a list of numbers, return all possible permutations.

Notice

You can assume that there is no duplicate numbers in the list.

For nums =[1,2,3], the permutations are:

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

Solution: Deep first search(Backtracking)

public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
        // write your code here
        if(nums == null)
            return new ArrayList<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> item = new ArrayList<Integer>();
        boolean[] visited = new boolean[nums.size()];
        dfs(nums, res, item, visited);
        return res;
    }
    public void dfs(ArrayList<Integer> nums,
                                 ArrayList<ArrayList<Integer>> res,
                                 ArrayList<Integer> item,
                                 boolean[] visited)
    {
        if(item.size() == nums.size()) {
            res.add(new ArrayList<>(item));
            return ;
        }
        for(int i = 0; i < nums.size(); i++) {
            if(visited[i])
                continue;
            item.add(nums.get(i));
            visited[i] = true;
            dfs(nums, res, item, visited);
            visited[i] = false;
            item.remove(item.size() - 1);       
        }
    }

Permutations II

Given a list of numbers with duplicate number in it. Find all unique permutations.

Solution: Skip duplicate numbers.

public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
        // write your code here
        if(nums == null)
            return new ArrayList<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> item = new ArrayList<Integer>();
        boolean[] visited = new boolean[nums.size()];
        dfs(nums, res, item, visited);
        return res;
    }
    public void dfs(ArrayList<Integer> nums,
                                 ArrayList<ArrayList<Integer>> res,
                                 ArrayList<Integer> item,
                                 boolean[] visited)
    {
        if(item.size() == nums.size()) {
            res.add(new ArrayList<>(item));
            return ;
        }
        for(int i = 0; i < nums.size(); i++) {
            //first number must be first use
            if(i > 0 && nums.get(i) == nums.get(i - 1) && !visited[i - 1]) {
                continue;
            }
            if(visited[i])
                continue;
            item.add(nums.get(i));
            visited[i] = true;
            dfs(nums, res, item, visited);
            visited[i] = false;
            item.remove(item.size() - 1);       
        }
    }