# Easy solution using code in nextPermutation

• Well, have you solved the Next Permutation problem? If so and you have handled the cases of duplicates at that problem, your code can be used in this problem. The idea is fairly simple:

1. sort `nums` in ascending order, add it to `res`;
2. generate the next permutation of `nums` using `nextPermutation()`, and add it to `res`;
3. repeat 2 until the next permutation of `nums` returns to the sorted condition in 1.

The code is as follows. For more about the idea of `nextPermutation()`, please visit this solution.

``````    bool nextPermutation(vector<int>& nums) {
int k = -1;
for (int i = nums.size() - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
k = i;
break;
}
}
if (k == -1) {
sort(nums.begin(), nums.end());
return false;
}
int l = -1;
for (int i = nums.size() - 1; i > k; i--) {
if (nums[i] > nums[k]) {
l = i;
break;
}
}
swap(nums[k], nums[l]);
reverse(nums.begin() + k + 1, nums.end());
return true;
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int> > res;
sort(nums.begin(), nums.end());
res.push_back(nums);
while (nextPermutation(nums))
res.push_back(nums);
return res;
}
``````

• Same logic without using sort and reverse function

``````    bool next_permutation(vector<int>& nums)
{
int i=0, j=nums.size()-1;

while(j>0 && nums[j]<=nums[j-1])
j--;
if(j==0)
return false;
int m=j,n=nums.size()-1;
j--;
while(m<n)
{
swap(nums[m++],nums[n--]);
}
int k=j+1;

while(k<nums.size() && nums[k]<=nums[j])
k++;
if(k<nums.size())
swap(nums[k],nums[j]);
return true;
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
res.push_back(nums);
while(next_permutation(nums))
res.push_back(nums);

return res;
}``````

• Java version I wrote on my own, which is super slow... Definitely not recommended.

Maybe the conversion process from array to list makes it so slow.

``````public class Solution {
public List<List<Integer>> permute(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList();
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
while (permuteNext(nums)) {
List<Integer> list1 = Arrays.stream(nums).boxed().collect(Collectors.toList());
}
return res;
}

private boolean permuteNext(int[] nums) {
int n = nums.length;
int k = n - 1, l = n - 1;
while (k > 0 && nums[k] <= nums[k - 1])
k--;
if (--k < 0) {
reverse(nums, 0, n - 1);
return false;
}
while (l > k && nums[l] < nums[k])
l--;
nums[k] ^= nums[l];
nums[l] ^= nums[k];
nums[k] ^= nums[l];
reverse(nums, k + 1, n - 1);
return true;
}

private void reverse(int[] nums, int start, int end) {
while (start < end) {
nums[start] ^= nums[end];
nums[end] ^= nums[start];
nums[start] ^= nums[end];
start++;
end--;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.