package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
    Example 1:

    Input: nums = [1,1,2]
    Output:
    [[1,1,2],
     [1,2,1],
     [2,1,1]]
     
    Example 2:
    
    Input: nums = [1,2,3]
    Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
**/
public class PermutationsII {

    class Solution {
        public List permuteUnique(int[] nums) {

            List result = new ArrayList();
            List list = new ArrayList();//first list
            for (int n : nums) {
                list.add(n);
            }
            backtrack(0, nums, list, result);
            return result;
        }

        public void backtrack(int index, int[] nums, List list, List result) {
            if (index == list.size() && !result.contains(list)) { // last tree branch issue
                //the recursion start swaping from last element
                result.add(new ArrayList(list));//copy and add
            }
            for (int i = index; i < nums.length; i++) {
                swap(list, index, i);//swap all other with this index
                backtrack(index + 1, nums, list, result);
                swap(list, index, i);//reset
            }
        }

        private void swap(List list, int index1, int index2) {
            int temp = list.get(index1);
            list.set(index1, list.get(index2));
            list.set(index2, temp);
        }
    }

    //Alternate Optimized
    class Solution2 {
        public List permuteUnique(int[] nums) {
            List res = new ArrayList();
            Arrays.sort(nums);
            boolean[] visited = new boolean[nums.length];
            helper(nums, res, new ArrayList(), visited);
            return res;
        }
        public void helper(int[] nums, List res, List ans, boolean[] visited) {
            if (ans.size() == nums.length) {
                res.add(new ArrayList(ans));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                if (visited[i] || i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                    continue;
                }
                ans.add(nums[i]);
                visited[i] = true;
                helper(nums, res, ans, visited);
                ans.remove(ans.size() - 1);
                visited[i] = false;
            }
        }
    }
}