Leetcode 267 Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

Solution 1:  Use back tracking, O((n/2)!) complexity.

 public class Solution {  
   public List<String> generatePalindromes(String s) {  
     int n=s.length();  
     int[] count=new int[256];  
     List<String> res=new ArrayList<>();  
     for (int i=0; i<n; i++) count[s.charAt(i)]++;  
     int odd=0;  
     for (int i=0; i<256; i++) {  
       if (count[i]%2!=0 && ++odd>1) return res;  
     }  
     char[] c=new char[n];  
     dfs(c,0,n-1,count,res);  
     return res;  
   }  
   private void dfs(char[] c, int lo, int hi, int[] count, List<String> res) {  
     if (lo>hi) res.add(new String(c));  
     else if (lo==hi) {  
       for (char i=0; i<256; i++) {  
         if (count[i]!=0) {  
           c[lo]=i;  
           res.add(new String(c));  
         }  
       }  
     }  
     else {  
       for (char i=0; i<256; i++) {  
         if (count[i]>=2) {  
           count[i]-=2;  
           c[lo]=i;  
           c[hi]=i;  
           dfs(c,lo+1,hi-1,count,res);  
           count[i]+=2;  
         }  
       }  
     }  
   }  
 }