排列

输入一个字符串，打印出该字符串中字符的所有排列。

排列算法基于交换，将当前项与后面的每一项都进行一次交换，就都是一次排列。
组合算法基于选择，需要新开一个 集合，将一项加入到集合后，还要将后面的项再加进来，集合 大小满足要求后，就是一次组合。

首先需要知道到如何使用递归求出排列，index从0开始：

    public void permutation(char[] c, int index) {
        if (index == c.length - 1) {
            new String(c);
        } else {
            for (int i = index; i < c.length; i++) {
                swap(c, index, i);
                permutation(c, index + 1);
                swap(c, index, i);
            }
        }
    }

如果数组中有重复的字母，需要使用一个HashSet去重：

class Solution {
    private char[] array;
    private LinkedList<String> list = new LinkedList<>();
    public String[] permutation(String s) {
        array = s.toCharArray();
        recur(0);
        return list.toArray(new String[list.size()]);
    }

    private void recur(int index) {
        if (index == array.length - 1) list.add(new String(array));
        HashSet<Character> set = new HashSet<>();
        for (int i = index; i < array.length; i++) {
            if (set.contains(array[i])) continue;
            set.add(array[i]);
            swap(index, i);
            recur(index + 1);
            swap(index, i);
        }
    }

    private void swap(int i, int j) {
        char tmp = array[i];
        array[i] = array[j];
        array[j]= tmp;
    }
}

组合

返回 1 ... n 中所有可能的 k 个数的组合。(leetcode-77)

class Solution {
    int n;
    int k;
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        combine(1, new LinkedList<Integer>());
        return res;
    }

    private void combine(int i, LinkedList<Integer> list) {
        if (list.size() == k) {
            res.add(new LinkedList<>(list));
            return；
        }
        for (int j = i; j <=n; j++) {
            list.add(j);
            combine(j + 1, list);
            list.removeLast();
        }
    }
}