package cn.fmachine.lintcode.medium;

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

/**
 * Given a list of numbers with duplicate number in it. Find all unique permutations.
 * <p>
 * Have you met this question in a real interview? Yes
 * Example
 * For numbers [1,2,2] the unique permutations are:
 * <p>
 * [
 * [1,2,2],
 * [2,1,2],
 * [2,2,1]
 * ]
 * Challenge
 * Using recursion to do it is acceptable. If you can do it without recursion, that would be great!
 * <p>
 * Tags
 * LinkedIn Recursion Depth First Search
 * Related Problems
 * Medium Next Permutation II 33 %
 * Medium Permutation Sequence 27 %
 * Medium Next Permutation 23 %
 * Medium Permutations
 * <p>
 * algorithm
 * Author: XIN MING
 * Date: 10/17/16
 *
 * time O(n!)
 */
public class PermutationsII {
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        ArrayList<List<Integer>> result = new ArrayList<>();
        if (nums == null) return result;
        if (nums.length == 0) {
            result.add(new ArrayList<Integer>());
            return result;
        }
        Arrays.sort(nums); //
        boolean[] visited = new boolean[nums.length];
        List<Integer> subset = new ArrayList<>();
        helper(nums, result, subset, visited);
        return result;
    }

    private void helper(int[] nums, ArrayList<List<Integer>> result,
                        List<Integer> subset, boolean[] visited) {
        if (subset.size() == nums.length) {
            result.add(new ArrayList<>(subset));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 对于重复的元素必须顺序访问才有效 如1，2，2 ： 1和第一个2组合时合法的subset，1和第二个2组合则非法
            // 所以对于一下情况直接跳过
            // 如果该元素已经访问过了
            // 或者虽然没有访问过，但是和前面的元素重复，且前面的元素没有访问过，这是需下标大于等于1，因为0没有前面的元素会越界
            if (visited[i] || i != 0 && nums[i] == nums[i - 1] && !visited[i - 1])
                continue;

            visited[i] = true;
            subset.add(nums[i]);
            helper(nums, result, subset, visited);
            subset.remove(subset.size() - 1);
            visited[i] = false;
        }
    }
}
