# Permutation, Subset, All group of Palindrome

By | October 23, 2015
Share the joy
•
•
•
•
•
•

Today, I found a great coding style for series problem, like permutation, subset and group of palindrome:

```public static void getPermutationUtil(String str, int start, List<List<String>> result, List<String> currResult) {
if(start==str.length()) {
ArrayList<String> curr = new ArrayList<String>(currResult);
result.add(curr);
}
else {
for(int i=start; i<str.length(); i++) {
String currStr = str.substring(start, i+1);
currResult.add(currStr);
getPermutationUtil(str, i + 1, result, currResult);
currResult.remove(currResult.size()-1);
}
}
}```

When we construct a subset of an array, we try to build it on arr[start,…,length-1]. The arr[0,…,i-1] is already done and saved in currResult. When start equals length, it means it ends and we save this currResult in result. Below are the 3 types of application of this coding style:
Permutation

```public static List<List<String>> getPermutation(String str) {
List<List<String>> result = new ArrayList<List<String>>();
getPermutationUtil(str, 0, result, new ArrayList<String>());
return result;
}

public static void getPermutationUtil(String str, int start, List<List<String>> result, List<String> currResult) {
if(start==str.length()) {
ArrayList<String> curr = new ArrayList<String>(currResult);
result.add(curr);
}
else {
for(int i=start; i<str.length(); i++) {
String currStr = str.substring(start, i+1);
currResult.add(currStr);
getPermutationUtil(str, i + 1, result, currResult);
currResult.remove(currResult.size()-1);
}
}
}```

SuperSet, This is the same problem from here, which is a another solution.

```public static List<List<Character>> getSuperSet(char[] chs) {
List<List<Character>> result = new ArrayList<List<Character>>();
getSuperSetUtil(chs, 0, result, new ArrayList<Character>());
return result;
}

public static void getSuperSetUtil(char[] chs, int start, List<List<Character>> result, List<Character> currResult) {
if(start==chs.length) {
ArrayList<Character> curr = new ArrayList<Character>(currResult);
result.add(curr);
}
else {
//count current char
currResult.add(chs[start]);
getSuperSetUtil(chs, start + 1, result, currResult);
currResult.remove(currResult.size()-1);
//doesn't count current char
getSuperSetUtil(chs, start+1, result, currResult);
}
}

public static void printSuperSet(char[] chs) {
List<List<Character>> sets = new ArrayList<List<Character>>();
int size = (int)Math.pow(2, chs.length);
for(int i=0; i<size; i++) {
List<Character> list = new ArrayList<Character>();
for(int j=0; j<chs.length; j++) {
if(((1<<j)&i)>0) {
list.add(chs[j]);
}
}
sets.add(list);
}
System.out.println(sets);
}```

All Palindrome Partition

```public static List<List<String>> getAllPalindromePartition(String str) {
List<List<String>> result = new ArrayList<List<String>>();
getAllPalindromePartitionUtil(str, 0, result, new ArrayList<String>());
return result;
}

public static void getAllPalindromePartitionUtil(String str, int start, List<List<String>> result, List<String> currResult) {
if(start==str.length()) {
ArrayList<String> curr = new ArrayList<String>(currResult);
result.add(curr);
}
else {
for(int i=start; i<str.length(); i++) {
String currStr = str.substring(start, i+1);
if(isPalindrome(currStr)) {
currResult.add(currStr);
getAllPalindromePartitionUtil(str, i + 1, result, currResult);
currResult.remove(currResult.size()-1);
}
}
}
}

public static boolean isPalindrome(String str) {
int left=0, right=str.length()-1;
while(left<right) {
if(str.charAt(left)==str.charAt(right)) {
left++;
right--;
}
else {
return false;
}
}
return true;
}```

Check my code on github:Permutation, Subset, All palindrome sets