注意不能重复

字符串的全排列

题解

可以将字符串分为两个部分，第一个字符和剩下其他的字符，先确定第一个字符的所有可能结果，即先与自身交换再剩下的其他字符逐一交换，每交换完一次就相当于确定了一个字符，接着需要确定下一个字符即第二个字符，让它再与自身交换然后与它之后的字符逐一交换……

代码

import java.util.ArrayList;
import java.util.TreeSet;
public class Solution {
    public ArrayList<String> strList = new ArrayList<>();
    public TreeSet<String> treeList = new TreeSet<>();

    public ArrayList<String> Permutation(String str) {
       if (str == null || str.length() <= 0)
           return strList;
        Permutation(str.toCharArray(), 0);
        for (String s : treeList)
            strList.add(s);
        return strList;
    }

    public void Permutation (char[] str, int index) {
        int length = str.length;
        if (index == length - 1)
            treeList.add(String.valueOf(str));
        else {
            for (int i = index; i < length; ++i) {
                swap(str, index, i);
                Permutation(str, index + 1);
                swap(str, index, i);
            }
        }
    }

    public void swap(char[] str, int a, int b) {
        char temp = str[a];
        str[a] = str[b];
        str[b] = temp;
    }
}

拓展：字符串的全组合

题解

代码

package com.ittyx;

import java.util.ArrayList;

public class ExtraCombination28ver02 {

    public static int[] A = {1, 2, 3, 4};

    public static void main(String[] args) {
        for (int i = 1; i <= A.length; i++) {
            ArrayList<Integer> result = new ArrayList<>();
            getCombination(i, 0, result);
        }
    }

    public static void getCombination(int m, int start, ArrayList<Integer> result) {
        if (m == 0) {
            //m个元素已经找齐，则打印
            for (Integer i : result) {
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }
        if (start < A.length) {
            result.add(A[start]);
            //使用A[start[，从剩下的(n-start+1)个元素中找m - 1个元素求它的组合
            getCombination(m - 1, start + 1, result);
            //不使用A[start]，从剩下(n-start+1)个元素中找m个元字符，求它的组合
            result.remove(result.size() - 1);//删掉本次添加的元素
            getCombination(m, start + 1, result);
        }
    }
}