# 267    Palindrome Permutation II

## 267. [Palindrome Permutation II](https://leetcode.com/problems/palindrome-permutation-ii/description/)

## 1. Question

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`[]`.

## 2. Implementation

**(1) Backtracking**

```java
class Solution {
    public List<String> generatePalindromes(String s) {
        List<String> res = new ArrayList<>();
        int[] map = new int[256];
        int odd = 0;

        for (char c : s.toCharArray()) {
            ++map[c];
            odd += (map[c] & 1) == 1 ? 1 : -1;
        }

        if (odd > 1) {
            return res;
        }

        String mid = "";
        int len = 0;

        for (int i = 0; i < 256; i++) {
            if (map[i] > 0) {
                if ((map[i] & 1) == 1) {
                    mid = "" + (char)i;
                    --map[i];
                }
                map[i] /= 2;
                len += map[i];
            }
        }

        getPalindromePermutations("", mid, map, len, res);
        return res;
    }

    public void getPalindromePermutations(String curStr, String mid, int[] map, int len, List<String> res) {
        if (curStr.length() == len) {
            String revStr = new StringBuilder(curStr).reverse().toString();
            res.add(curStr + mid + revStr);
            return;
        }

        for (int i = 0; i < 256; i++) {
            if (map[i] > 0) {
                --map[i];
                getPalindromePermutations(curStr + (char)i, mid, map, len, res);
                ++map[i];
            }
        }
    }
}
```

## 3. Time & Space Complexity

**Backtracking:** 时间复杂度O((n/2)!), 空间复杂度O(n), 递归的深度最多为n/2