# One simple method that solves many similar problems

• First, you need to recall that such problems can be solved with backtracking, i.e. every time you fall into the next level of your recursion where you need to follow the same procedure but with the result of the previous step in your mind.

In this particular problem, remember the number that you have chosen in the previous step (in the upper level of the recursion). This can be done using regular boolean array where each index shows if the corresponding index in the numbers array is used or not. So if the index is set to true, then the number at that index has already been used and added to the running list. So simply select the next unset number in your numbers array. The problem here though is that the numbers may repeat, i.e. having repeated elements leads to duplicate lists in your answer. In order to take care of it, recall the solutions from https://leetcode.com/problems/combination-sum-ii/description/ and https://leetcode.com/problems/permutations/. The combination of their solutions lead to a simple but elegant solution.

I attach the full code below with some description.

``````class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null) {
return new ArrayList<>();
}

Arrays.sort(nums); // sort to take care of duplicates
List<List<Integer>> combs = new ArrayList<>(); // final answer
permuteHelper(combs, new ArrayList<>(), new boolean[nums.length], nums);

return combs;
}

private void permuteHelper(List<List<Integer>> combs, List<Integer> runningList,
boolean[] used, int[] nums) {
if (runningList.size() == nums.length) {  // if we have all the numbers in the list
return;
}

boolean firstSeen = false; // if we have seen the first unused element
int lastSeen = nums[0]; // what is the last seen element in the array

for (int i = 0; i < nums.length; i++) {
if (firstSeen && nums[i] == lastSeen) {
continue;
}
if (used[i]) {
continue;
}

firstSeen = true; // this is the first unused element
lastSeen = nums[i]; // lastSeen is the current unused element
used[i] = true;