Simple Java Solution (Slight Modification to Permute Algo)

• Basic permutation algorithm with a simple change to maintain lexicographic order.

Algo

• list itemThe idea is to pick up 'ith' element and push all the elements to their right by one position to make room for it at 'begin' position.

• list itempermue the array to its right

• list itemRestore the original array (i.e pull back all elements to the left by one position to make room for nums[begin] at ith position)

Please note that push and pull elements in the array will not change the overall time complexity since n < n!

``````class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
permute(nums, 0, list);
return list;
}
private List<Integer> getList(int[] a) {
List<Integer> list = new ArrayList<>();
for (int i : a) {
list.add(i);
}
return list;
}
public void permute(int[] a, int begin, List<List<Integer>> list) {
if (begin == a.length - 1) {
list.add(getList(a));
return;
}
for (int i = begin; i < a.length; i++) {
put_i_at_begin(a, begin, i);
permute(a, begin + 1, list);
restore(a, begin, i);
}
}

private void restore(int[] a, int i, int j) {
int tmp = a[i];
while (i < j) {
a[i] = a[i + 1];
i++;
}
a[j] = tmp;
}
private void put_i_at_begin(int[] a, int begin, int i) {
int tmp = a[i];
while (i > begin) {
a[i] = a[i - 1];
--i;
}
a[begin] = tmp;
}
}
``````

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