数字子集的排列组合问题

• Combinations

https://leetcode.com/problems/combinations/
给定N和K，确定1~N的整数中取出K个数字的排列

相似题：permutation(全排列)

  public List<List<Integer>> combine(int n, int k) {
        List<Integer> input = new ArrayList<Integer>();
        List<Integer> out = new ArrayList<Integer>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int[] visited = new int[n];
        int level = 0;
        for (int i = 0; i < visited.length; i++) {
            visited[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            input.add(i + 1);
        }
        combineHelper(input, level, k, out, res);
        return res;
    }

    public void combineHelper(List<Integer> input, int level, int k, List<Integer> out, List<List<Integer>> res) {
        if (out.size() == k) {
            res.add(new ArrayList<Integer>(out));
            return;
        }

        for (int i = level; i < input.size(); i++) {

            out.add(input.get(i));

            combineHelper(input, i + 1, k, out, res);
            out.remove(out.size() - 1);
        }
    }

• Subset

https://leetcode.com/problems/subsets/
给定一个数组，求出这个数组的所有子集。（与Combination比较类似）

  public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> input = new ArrayList<Integer>();

        for (int i = 0; i < nums.length; i++) {
            input.add(nums[i]);
        }
        for (int k = 0; k <= nums.length; k++) {
            int level = 0;
            List<Integer> out = new ArrayList<Integer>();
            subsetHelper(nums, level, k, out, res);
        }
        return res;
    }

    public void subsetHelper(int[] input, int level, int k, List<Integer> out, List<List<Integer>> res) {
        if (out.size() == k) {
            res.add(new ArrayList<Integer>(out));
            return;
        }

        for (int i = level; i < input.length; i++) {

            out.add(input[i]);

            subsetHelper(input, i + 1, k, out, res);
            out.remove(out.size() - 1);
        }
    }

• Subset ii
  subset的扩展，这一题nums里面有重复的数字

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> out = new ArrayList<Integer>();
        Arrays.sort(nums);
        getSubsetsDup(nums, 0, out, res);
        return res;
    }

    public void getSubsetsDup(int[] nums, int level, List<Integer> out, List<List<Integer>> res) {
        res.add(new ArrayList<Integer>(out));
        for (int i = level; i < nums.length; i++) {
            out.add(nums[i]);
            getSubsetsDup(nums, i + 1, out, res);
            out.remove(out.size() - 1);

            while (i + 1 < nums.length && nums[i] == nums[i + 1]) {
                i++;
            }
        }
    }