排列与组合.md

    // 组合
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        int[] temp = new int[k];
        comb(nums, 0, temp, 0, res);
        return res;
    }

    void comb(int[] arr, int start, int[] tmp, int cnt,
            List<List<Integer>> res) {

        if (cnt >= tmp.length) {
            List<Integer> item = new ArrayList<Integer>(tmp.length);
            for (int i = 0; i < tmp.length; i++) {
                item.add(tmp[i]);
            }
            res.add(item);
        } else {
            for (int i = start; i < arr.length; i++) {
                tmp[cnt] = arr[i];
                comb(arr, i + 1, tmp, cnt + 1, res);

            }
        }
    }

    // 排列
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        perm(nums, 0, res);
        return res;
    }

    void perm(int[] arr, int k, List<List<Integer>> res) {
        final int LEN = arr.length;
        if (k >= LEN) {
            List<Integer> item = new ArrayList<Integer>(LEN);
            for (int i = 0; i < LEN; i++) {
                item.add(arr[i]);
            }
            res.add(item);
        } else {
            for (int i = k; i < LEN; i++) {
                exch(arr, i, k);
                perm(arr, k + 1, res);
                exch(arr, i, k);
            }
        }
    }

    // 交换
    void exch(int[] arr, int lo, int hi) {

        int tmp = arr[lo];
        arr[lo] = arr[hi];
        arr[hi] = tmp;
    }