LeetCode - Subsets
Related: LeetCode 47 - Permutations II
Given a collection of numbers, return all possible permutations.
For example, [1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]
http://yucoding.blogspot.com/2013/04/leetcode-question-69-permutations.html
Consider:
a --> a
ab --> ab, ba
abc --> abc, acb, bac, bca, cab, cba.
...
where for the length of n, the permutations can be generated by
(1) Swap the 1st element with all the elements, including itself.
(2) Then the 1st element is fixed, go to the next element.
(3) Until the last element is fixed. Output.
Iterative Version
Loop through the array, in each iteration, a new number is added to different locations of results of previous iteration. Start from an empty List.
https://discuss.leetcode.com/topic/10812/share-my-short-iterative-java-solution
就是遍历nums(第一个for loop),当开始进行nums[i]时,res中的结果是nums[0]至nums[i-1]的全排列。每一次循环中,需要将nums[i]加入到res中的每一个结果中的每一个位置,然后开始下一次循环。具体做法是,每一次循环开始,先记录当前res的大小(size),取出res中的第一个,在每个位置添加nums[i]然后加到res末尾(第三个for loop,循环r.size()次),一共进行size次(第二个for loop)
t.add(i, n); is very expensive. The time complexity is O(n!*n)
https://discuss.leetcode.com/topic/10812/share-my-short-iterative-java-solution
与subset I的方法2很相近。以题中例子说明:
当只有1时候:[1]
当加入2以后:[2, 1], [1, 2]
当加入3以后:[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]
前3个permutation分别对应将3插入[2, 1]的0, 1, 2的位置。同理后3个为插入[1, 2]的。因此可以用逐个插入数字来构造所有permutation.
[leetcode] Permutations | 一个array的所有permutation
上面的代码有时候乍一看可能觉得只有两层循环,时间复杂度是不是O(n^2)之类的。事实上肯定不是的,因为注意第二层循环是对于res进行遍历的,而res是一直在以平方量级增长的,所以总的时间复杂度还是会是指数量级以上的。
https://leetcode.com/discuss/19510/my-ac-simple-iterative-java-python-solution
X. DFS
https://discuss.leetcode.com/topic/46162/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partioning
Bottom up approach
https://discuss.leetcode.com/topic/23036/java-clean-code-two-recursive-solutions
public class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new LinkedList<List<Integer>>(); if(nums.length == 0) return result; List<Integer> cur = new LinkedList<Integer>(); cur.add(nums[0]); result.add(cur); for(int i = 1; i < nums.length; i++) { int curSize = result.size(); for(int j = 0; j < curSize; j++) { for(int x = 0; x < result.get(j).size(); x++) { List<Integer> newList = new LinkedList<Integer>(result.get(j)); newList.add(x, nums[i]); result.add(newList); } result.get(j).add(nums[i]); } } return result; } }
http://xiaohuiliucuriosity.blogspot.com/2014/12/permutations.html
Recursive Version:
https://discuss.leetcode.com/topic/23036/java-clean-code-two-recursive-solutions
Also refer to http://blog.csdn.net/u010500263/article/details/18178243
http://yucoding.blogspot.com/2013/04/leetcode-question-69-permutations.html
P(a1 a2a3 ) = {a1 + P(a2a3 )} + a2 + P(a1a)} + {a3 + P(a1a2 )}
{a1 + P(a2a3 )} -> a1a2a3 , a1a3 a2
{ a2 + P( a1a)} - > a2 a1 a3 , a2 a3a1
{a3 + P(a1 a)} -> a3 a1 a2 , a3 a2 a1
P(a1a2a3 a4 ) = {a1 + P(a2a3a4 )} + {a2 + P(a1a,a4 )} + {a, + P(a1a2a4 )} + {a4 + P(a1a2a,)}
Arraylist<String> getPerms(String remainder) {
int len - remainder.length();
ArrayList<String> result= new ArrayList<String>();
/* Base case. */
if (len == 0) {
}
result.add(""); // Be sure to return empty string!
return result;
for (int i= 0; i < len; i++) {
/* Remove char i and find permutations of remaining chars.*/
String before= remainder.substring(0, i);
String after = remainder.substring(i + 1, len);
Arraylist<String> partials = getPerms(before + after);
/* Prepend char i to each permutation.*/
for (String s : partials) {
result.add(remainder.charAt(i) + s);
}
}
return result;
}
https://leetcode.com/problems/permutations/discuss/18436/Java-Clean-Code-Two-recursive-solutions
Read full article from LeetCode - Permutations | Darren's Blog
Related: LeetCode 47 - Permutations II
Given a collection of numbers, return all possible permutations.
For example, [1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]
http://yucoding.blogspot.com/2013/04/leetcode-question-69-permutations.html
Consider:
a --> a
ab --> ab, ba
abc --> abc, acb, bac, bca, cab, cba.
...
where for the length of n, the permutations can be generated by
(1) Swap the 1st element with all the elements, including itself.
(2) Then the 1st element is fixed, go to the next element.
(3) Until the last element is fixed. Output.
Iterative Version
Loop through the array, in each iteration, a new number is added to different locations of results of previous iteration. Start from an empty List.
https://discuss.leetcode.com/topic/10812/share-my-short-iterative-java-solution
就是遍历nums(第一个for loop),当开始进行nums[i]时,res中的结果是nums[0]至nums[i-1]的全排列。每一次循环中,需要将nums[i]加入到res中的每一个结果中的每一个位置,然后开始下一次循环。具体做法是,每一次循环开始,先记录当前res的大小(size),取出res中的第一个,在每个位置添加nums[i]然后加到res末尾(第三个for loop,循环r.size()次),一共进行size次(第二个for loop)
t.add(i, n); is very expensive. The time complexity is O(n!*n)
public List<List<Integer>> permute(int[] num) {
LinkedList<List<Integer>> res = new LinkedList<List<Integer>>();
res.add(new ArrayList<Integer>());
for (int n : num) {
int size = res.size();
for (; size > 0; size--) {
List<Integer> r = res.pollFirst();
for (int i = 0; i <= r.size(); i++) {
List<Integer> t = new ArrayList<Integer>(r);
t.add(i, n);
res.add(t);
}
}
}
return res;
}
https://discuss.leetcode.com/topic/6377/my-ac-simple-iterative-java-python-solutionhttps://discuss.leetcode.com/topic/10812/share-my-short-iterative-java-solution
the basic idea is, to permute n numbers, we can add the nth number into the resulting
List<List<Integer>>
from the n-1 numbers, in every possible position.
For example, if the input num[] is {1,2,3}: First, add 1 into the initial
List<List<Integer>>
(let's call it "answer").
Then, 2 can be added in front or after 1. So we have to copy the List<Integer> in answer (it's just {1}), add 2 in position 0 of {1}, then copy the original {1} again, and add 2 in position 1. Now we have an answer of {{2,1},{1,2}}. There are 2 lists in the current answer.
Then we have to add 3. first copy {2,1} and {1,2}, add 3 in position 0; then copy {2,1} and {1,2}, and add 3 into position 1, then do the same thing for position 3. Finally we have 2*3=6 lists in answer, which is what we want.
public List<List<Integer>> permute(int[] num) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if (num.length ==0) return ans;
List<Integer> l0 = new ArrayList<Integer>();
l0.add(num[0]);
ans.add(l0);
for (int i = 1; i< num.length; ++i){
List<List<Integer>> new_ans = new ArrayList<List<Integer>>();
for (int j = 0; j<=i; ++j){
for (List<Integer> l : ans){
List<Integer> new_l = new ArrayList<Integer>(l);
new_l.add(j,num[i]);
new_ans.add(new_l);
}
}
ans = new_ans;
}
return ans;
}
与subset I的方法2很相近。以题中例子说明:
当只有1时候:[1]
当加入2以后:[2, 1], [1, 2]
当加入3以后:[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]
前3个permutation分别对应将3插入[2, 1]的0, 1, 2的位置。同理后3个为插入[1, 2]的。因此可以用逐个插入数字来构造所有permutation.
[leetcode] Permutations | 一个array的所有permutation
public ArrayList<ArrayList<Integer>> permute(int[] num) { ArrayList<ArrayList<Integer>> lastLayer = new ArrayList<ArrayList<Integer>>(); lastLayer.add(new ArrayList<Integer>()); for (int i = 0; i < num.length; i++) { ArrayList<ArrayList<Integer>> newLayer = new ArrayList<ArrayList<Integer>>(); for (int j = 0; j < lastLayer.size(); j++) { ArrayList<Integer> curr = lastLayer.get(j); insertEverywhere(curr, num[i], newLayer); } lastLayer = newLayer; // switch pointers instead of copy } return lastLayer; } private void insertEverywhere(ArrayList<Integer> curr, int num, ArrayList<ArrayList<Integer>> newLayer) { for (int i = 0; i <= curr.size(); i++) { ArrayList<Integer> newList = new ArrayList<Integer>(curr); newList.add(i, num); newLayer.add(newList); } }Code from http://www.programcreek.com/2013/02/leetcode-permutations-java/
public ArrayList<ArrayList<Integer>> permute(int[] num) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); //start from an empty list result.add(new ArrayList<Integer>()); for (int i = 0; i < num.length; i++) { //list of list in current iteration of the array num ArrayList<ArrayList<Integer>> current = new ArrayList<ArrayList<Integer>>(); for (ArrayList<Integer> l : result) { // # of locations to insert is largest index + 1 for (int j = 0; j < l.size()+1; j++) { ArrayList<Integer> temp = new ArrayList<Integer>(l);
temp .add(j, num[i]);
current.add(temp); } } result = new ArrayList<ArrayList<Integer>>(current); } return result; }http://blog.csdn.net/linhuanmars/article/details/21569031
上面的代码有时候乍一看可能觉得只有两层循环,时间复杂度是不是O(n^2)之类的。事实上肯定不是的,因为注意第二层循环是对于res进行遍历的,而res是一直在以平方量级增长的,所以总的时间复杂度还是会是指数量级以上的。
https://leetcode.com/discuss/19510/my-ac-simple-iterative-java-python-solution
the basic idea is, to permute n numbers, we can add the nth number into the resulting
List<List<Integer>>
from the n-1 numbers, in every possible position.
For example, if the input num[] is {1,2,3}: First, add 1 into the initial
List<List<Integer>>
(let's call it "answer").
Then, 2 can be added in front or after 1. So we have to copy the List in answer (it's just {1}), add 2 in position 0 of {1}, then copy the original {1} again, and add 2 in position 1. Now we have an answer of {{2,1},{1,2}}. There are 2 lists in the current answer.
Then we have to add 3. first copy {2,1} and {1,2}, add 3 in position 0; then copy {2,1} and {1,2}, and add 3 into position 1, then do the same thing for position 3. Finally we have 2*3=6 lists in answer, which is what we want.
we can optimize the solution by adding on to a single answer list instead of recreating a new list every time!X. DFS
https://discuss.leetcode.com/topic/46162/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partioning
Bottom up approach
https://discuss.leetcode.com/topic/23036/java-clean-code-two-recursive-solutions
Code flow
nums = 1,2,3
start = 0, permutation = []
i = 0, newPermutation = [1]
start = 1, permutation = [1]
i = 0, newPermutation = [2, 1]
start = 2, permutation = [2, 1]
i = 0, newPermutation = [3, 2, 1]
i = 1, newPermutation = [2, 3, 1]
i = 2, newPermutation = [2, 1, 3]
i = 1, newPermutation = [1, 2]
start = 2, permutation = [1, 2]
i = 0, newPermutation = [3, 1, 2]
i = 1, newPermutation = [1, 3, 2]
i = 2, newPermutation = [1, 2, 3]
https://leetcode.com/discuss/29483/share-my-short-iterative-java-solutionpublic class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new LinkedList<List<Integer>>(); if(nums.length == 0) return result; List<Integer> cur = new LinkedList<Integer>(); cur.add(nums[0]); result.add(cur); for(int i = 1; i < nums.length; i++) { int curSize = result.size(); for(int j = 0; j < curSize; j++) { for(int x = 0; x < result.get(j).size(); x++) { List<Integer> newList = new LinkedList<Integer>(result.get(j)); newList.add(x, nums[i]); result.add(newList); } result.get(j).add(nums[i]); } } return result; } }
I used your idea of adding each next value to every possible position of current list, but have done it with recursion. -- not
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums.length == 0) return result;
backtrack(result, nums, new ArrayList<Integer>(), 0);
return result;
}
private void backtrack(List<List<Integer>> result, int[] nums, List<Integer> currentList, int index) {
if (currentList.size() == nums.length) {
result.add(currentList);
return;
}
int n = nums[index];
for (int i = 0; i <= currentList.size(); i++) {
List<Integer> copy = new ArrayList<Integer>(currentList);
copy.add(i, n);
backtrack(result, nums, copy, index + 1);
}
}
https://leetcode.com/discuss/18212/my-elegant-recursive-c-solution-with-inline-explanationhttp://xiaohuiliucuriosity.blogspot.com/2014/12/permutations.html
Recursive Version:
https://discuss.leetcode.com/topic/42417/2ms-java-solution-beats-93-i-think-it-could-be-optimized
https://leetcode.com/problems/permutations/discuss/18470/My-Java-Accepted-solution-without-additional-space
https://leetcode.com/problems/permutations/discuss/18470/My-Java-Accepted-solution-without-additional-space
public List<List<Integer>> permute(int[] num) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
permute(result, num, 0);
return result;
}
private void permute(List<List<Integer>> result, int[] array, int start) {
if (start >= array.length) {
List<Integer> current = new ArrayList<Integer>();
for (int a : array) {
current.add(a);
}
result.add(current);
} else {
for (int i=start; i<array.length; i++) {
swap(array, start, i);
permute(result, array, start+1);
swap(array, start, i);
}
}
}
private void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
https://discuss.leetcode.com/topic/46162/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partioning
We can also recursively solve this problem. Swap each element with each element after it.
code from http://blog.csdn.net/u010500263/article/details/18178243
List<List<Integer>> list; public List<List<Integer>> permute(int[] nums) { list = new ArrayList<>(); ArrayList<Integer> perm = new ArrayList<Integer>(); backTrack(perm,0,nums); return list; } void backTrack (ArrayList<Integer> perm,int i,int[] nums){ //Permutation completes if(i==nums.length){ list.add(new ArrayList(perm)); return; } ArrayList<Integer> newPerm = new ArrayList<Integer>(perm); //Insert elements in the array by increasing index for(int j=0;j<=i;j++){ newPerm.add(j,nums[i]);// this is slow backTrack(newPerm,i+1,nums); newPerm.remove(j); } }
X. DFS
We can also recursively solve this problem. Swap each element with each element after it.
public ArrayList<ArrayList<Integer>> permute(int[] num) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); permute(num, 0, result); return result; } void permute(int[] num, int start, ArrayList<ArrayList<Integer>> result) { if (start >= num.length) { ArrayList<Integer> item = new ArrayList(num); result.add(item); } for (int j = start; j <= num.length - 1; j++) { swap(num, start, j); //\\ key permute(num, start + 1, result); swap(num, start, j); //\\ } } private void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }X. Use boolean visited array: add/remove
code from http://blog.csdn.net/u010500263/article/details/18178243
public ArrayList<ArrayList<Integer>> permute(int[] num) {ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();ArrayList<Integer> element = new ArrayList<Integer>();boolean[] visited = new boolean[num.length];helper(num, result, element, visited);return result;}public void helper(int[] num, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> element, boolean[] visited) {if (element.size() == num.length) {// duplicate element and add it to result (element would be changed from time to// time. If directly use element// only result would be changed when element changed)result.add(new ArrayList<Integer>(element));return;}for (int i = 0; i < num.length; i++) {if (!visited[i]) {visited[i] = true;element.add(num[i]);helper(num, result, element, visited);// After providing a complete permutation, pull out the last number,element.remove(element.size() - 1);visited[i] = false;}}}
https://leetcode.com/discuss/55418/java-clean-code-two-recursive-solutions public class Solution {
public List<List<Integer>> permute(int[] nums) { List<List<Integer>> permutations = new ArrayList<>(); if (nums.length == 0) { return permutations; } collectPermutations(nums, 0, new ArrayList<>(), permutations); return permutations; } private void collectPermutations(int[] nums, int start, List<Integer> permutation, List<List<Integer>> permutations) { if (permutation.size() == nums.length) { permutations.add(permutation); return; } for (int i = 0; i <= permutation.size(); i++) { List<Integer> newPermutation = new ArrayList<>(permutation); newPermutation.add(i, nums[start]); collectPermutations(nums, start + 1, newPermutation, permutations); } } }https://leetcode.com/problems/permutations/discuss/18459/Java-solution-easy-to-understand-(backtracking)
List<List<Integer>> list; public List<List<Integer>> permute(int[] nums) { list = new ArrayList<>(); ArrayList<Integer> perm = new ArrayList<Integer>(); backTrack(perm,0,nums); return list; } void backTrack (ArrayList<Integer> perm,int i,int[] nums){ //Permutation completes if(i==nums.length){ list.add(new ArrayList(perm)); return; } ArrayList<Integer> newPerm = new ArrayList<Integer>(perm); //Insert elements in the array by increasing index for(int j=0;j<=i;j++){ newPerm.add(j,nums[i]);// this is slow backTrack(newPerm,i+1,nums); newPerm.remove(j); } }
X. DFS
这种思路和思路1的区别是:思路1采用位置两两交换,交换后出现一种新的组合,将这种新的组合添加到中间集,再添加到结果集中。而这种思路是采用逐一向中间集添加元素,并将当中间集元素个数等于 nums 长度的时候,将中间集添加到结果集中,并终止该层递归:
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
dfs(res, new ArrayList<Integer>(), nums, new boolean[nums.length]);
return res;
}
private void dfs(List<List<Integer>> res, List<Integer> temp, int[] nums, boolean[] used) {
if (temp.size() == nums.length) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (!used[i]) {
used[i] = true;
temp.add(nums[i]);
dfs(res, temp, nums, used);
temp.remove(temp.size() - 1);
used[i] = false;
}
}
}
X. Base case and build approachhttps://discuss.leetcode.com/topic/23036/java-clean-code-two-recursive-solutions
public List<List<Integer>> permute(int[] nums) {
return permute(Arrays.stream(nums).boxed().collect(Collectors.toList()));
}
private List<List<Integer>> permute(List<Integer> nums) {
List<List<Integer>> permutations = new ArrayList<>();
if (nums.size() == 0) {
return permutations;
}
if (nums.size() == 1) {
List<Integer> permutation = new ArrayList<>();
permutation.add(nums.get(0));
permutations.add(permutation);
return permutations;
}
List<List<Integer>> smallPermutations = permute(nums.subList(1, nums.size()));
int first = nums.get(0);
for(List<Integer> permutation : smallPermutations) {
for (int i = 0; i <= permutation.size(); i++) {
List<Integer> newPermutation = new ArrayList<>(permutation);
newPermutation.add(i, first);
permutations.add(newPermutation);
}
}
return permutations;
}
X. http://www.geeksforgeeks.org/permutations-string-using-iteration/
Concept Used : We keep swapping a character only till it reaches the end
- Fix ‘a’. Swap ‘b’ with its next neighbors till b reaches the end.
( “acbd”, “acdb”) - Now ‘c’ will be at the 2nd position, do the same thing with it.
( “adcb”, “adbc”) - Now ‘d’ will be at the 2nd position, do the same thing with it.
( “abdc”, “abcd”) - All 6 i.e., (4!/4)permutations of the first cycle obtained.
- Repeat the above process by bringing swapping ‘a’ with ‘b’
- The new string to “play” will be “bacd”.
// A utility function to find n!
int
fact(
int
n)
{
return
(n==1)? 1 : n*fact(n-1);
}
// An iterative function to print all permutations of s.
void
printPermutation(string s)
{
// Find length of string and factorial of length
int
n = s.length();
int
fc = fact(n);
// Point j to the 2nd position
int
j = 1;
// To store position of character to be fixed next.
// m is used as in index in s[].
int
m = 0;
// Iterate while permutation count is
// smaller than n! which fc
for
(
int
perm_c = 0; perm_c < fc; )
{
// Store perm as current permutation
string perm = s;
// Fix the first position and iterate (n-1)
// characters upto (n-1)!
// k is number of iterations for current first
// character.
int
k = 0;
while
(k != fc/n)
{
// Swap jth value till it reaches the end position
while
(j != n-1)
{
// Print current permutation
cout << perm <<
"\n"
;
// Swap perm[j] with next character
swap(perm[j], perm[j+1]);
// Increment count of permutations for this
// cycle.
k++;
// Increment permutation count
perm_c++;
// Increment 'j' to swap with next character
j++;
}
// Again point j to the 2nd position
j = 1;
}
// Move to next character to be fixed in s[]
m++;
// If all characters have been placed at
if
(m == n)
break
;
// Move next character to first position
swap(s[0], s[m]);
}
}
http://yucoding.blogspot.com/2013/04/leetcode-question-69-permutations.html
Approach 1: Building from permutations of first n-1 characters.
Arraylist<String> getPerms(String str) {
if (str == null) return null;
Arraylist<String> permutations new ArrayList<String>();
if (str.length() == 0) {//base case
permutations.add('"');
return permutations;
}
char first= str.charAt(0); // get the first char
String remainder= str.substring(l); // remove the first char
Arraylist<String> words= getPerms(remainder);
for (String word: words) {
for (int j = 0; j <= word.length(); +j +) {
String s= insertCharAt(word, first, j);
permutations.add(s);
}
}
return permutations;
}
/* Insert char c at index i in word. */
String insertCharAt(String word, char c, int i) {
String start= word.substring(0, i);
String end= word.substring(i);
return start+ c + end;
}
Approach 2: Building from permutations of all n-1 character substrings.
we just need to "try" each character as the first character and then append the permutations.P(a1 a2a3 ) = {a1 + P(a2a3 )} + a2 + P(a1a)} + {a3 + P(a1a2 )}
{a1 + P(a2a3 )} -> a1a2a3 , a1a3 a2
{ a2 + P( a1a)} - > a2 a1 a3 , a2 a3a1
{a3 + P(a1 a)} -> a3 a1 a2 , a3 a2 a1
P(a1a2a3 a4 ) = {a1 + P(a2a3a4 )} + {a2 + P(a1a,a4 )} + {a, + P(a1a2a4 )} + {a4 + P(a1a2a,)}
Arraylist<String> getPerms(String remainder) {
int len - remainder.length();
ArrayList<String> result= new ArrayList<String>();
/* Base case. */
if (len == 0) {
}
result.add(""); // Be sure to return empty string!
return result;
for (int i= 0; i < len; i++) {
/* Remove char i and find permutations of remaining chars.*/
String before= remainder.substring(0, i);
String after = remainder.substring(i + 1, len);
Arraylist<String> partials = getPerms(before + after);
/* Prepend char i to each permutation.*/
for (String s : partials) {
result.add(remainder.charAt(i) + s);
}
}
return result;
}
Arraylist<String> getPerms(String str) {
Arraylist<String> result = new Arraylist<String>();
getPerms("", str, result);
return result;
}
void getPerms(String prefix, String remainder, Arraylist<String> result) {
if (remainder.length()== 0) result.add(prefix);
int len = remainder.length();
for (int i= 0; i < len; i++) {
String before = remainder.substring(0, i);
String after = remainder.substring(i + 1, len);
char c = remainder.charAt(i);
getPerms(prefix + c, before + after, result);
}
}
Read full article from LeetCode - Permutations | Darren's Blog