Permutation

• https://leetcode.com/problems/permutations/
• https://leetcode.com/problems/permutations-ii/

Given a collection of numbers, return all possible permutations.

// Note: This code only work when all the numbers are unique
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList();
    if (nums == null || nums.length == 0)
        return result;
    helper(new ArrayList<Integer>(), result, nums);
    return result;
}

private void helper(List<Integer> current, List<List<Integer>> result, int[] nums) {
    if (current.size() == nums.length) {
        result.add(new ArrayList(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (!current.contains(nums[i])) {
            current.add(nums[i]);
            helper(current, result, nums);
            current.remove(current.size() - 1);
        }
    }
}

This method doens't have List current.

  public static List<List<Integer>> permutations(List<Integer> A) {
    List<List<Integer>> result = new ArrayList<>();
    directedPermutations(0, A, result);
    return result;
  }

  private static void directedPermutations(int i, List<Integer> A,
                                           List<List<Integer>> result) {
    if (i == A.size() - 1) {
      result.add(new ArrayList<>(A));
      return;
    }

    // Try every possibility for A[i].
    for (int j = i; j < A.size(); ++j) {
      Collections.swap(A, i, j);
      // Generate all permutations for A[i + 1 : A.size() - 1].
      directedPermutations(i + 1, A, result);
      Collections.swap(A, i, j);
    }
  }

This is identical to the above one except the argument is array.

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList();
    helper(nums, 0, result);
    return result;
}

private void helper(int[] nums, int currentIndex, List<List<Integer>> result) {
    if (currentIndex == nums.length) {
        List<Integer> current = new ArrayList();
        for (int i : nums) {
            current.add(i);
        }
        result.add(new ArrayList(current));
    } else {
        for (int i = currentIndex; i < nums.length; i++) {
            swap(nums, i, currentIndex);
            helper(nums, currentIndex + 1, result);
            swap(nums, i, currentIndex);
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
    return;
}

Permutation II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,

• [1,1,2] have the following unique permutations:
• [1,1,2], [1,2,1], and [2,1,1].

Solution: add a set to keep track of what has been added.

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        helper(nums, 0, result, new HashSet<List<Integer>>());
        return result;
    }

    private void helper(int[] nums, int currentIndex, List<List<Integer>> result, Set<List<Integer>> set) {
        if (currentIndex == nums.length) {
            List<Integer> current = new ArrayList();
            for (int i : nums) {
                current.add(i);
            }
            if (!set.contains(current)) {
                result.add(new ArrayList(current));
                set.add(current);
            }
        } else {
            for (int i = currentIndex; i < nums.length; i++) {
                swap(nums, i, currentIndex);
                helper(nums, currentIndex + 1, result, set);
                swap(nums, i, currentIndex);
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
        return;
    }

//TODO: not fully understand

public List<List<Integer>> permuteUnique(int[] nums) {
    Set<List<Integer>> resultSet = new HashSet();
    helper(0, nums, resultSet);
    return new ArrayList(resultSet);
}

private void helper(int start, int[] nums, Set<List<Integer>> resultSet) {
    if (start >= nums.length) {
        List<Integer> result = new ArrayList();
        for (int i : nums) {
            result.add(i);
        }
        resultSet.add(result);
        return;
    }

    for (int i = start; i < nums.length; i++) {
        // To avoid duplicate, we need to check the existing sequence first.
        if (isUnique(nums, start, i)) {
            swap(nums, start, i);
            helper(start + 1, nums, resultSet);
            swap(nums, start, i);    
        }
    }
}

private void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

private boolean isUnique(int[] array, int start, int end) {
    for (int i = start; i <= end-1; i++) {
        if (array[i] == array[end]) {
            return false;
        }
    }
    return true;
}

Sort the array first, ussing a boolean array to indicate which

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> result = new ArrayList();
    Arrays.sort(nums);
    boolean[] visited = new boolean[nums.length];
    helper(nums, new ArrayList<Integer>(), result, visited);
    return result;
}

private void helper(int[] nums, List<Integer> current, List<List<Integer>> result, boolean[] visited) {
    if (current.size() == nums.length) {
        result.add(new ArrayList(current));
    } else {
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            } 
            if (!visited[i]) {
                visited[i] = true;
                current.add(nums[i]);
                helper(nums, current, result, visited);
                current.remove(current.size() - 1);
                visited[i] = false;
            }

        }
    }
}