combination, subsets

List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> combine(int n, int k) {
    if (n == 0)
        return ans;
    int[] nums = new int[n];
    for (int i = 0; i < n; ++i) {
        nums[i] = i + 1;
    }
    List<Integer> path = new ArrayList<Integer>();
    dfs(nums, path, 0, k);
    return ans;
}

public void (int[] nums, List<Integer> path, int begin, int k) {
    if (path.size() == k) {
        ans.add(new ArrayList<Integer>(path));
        return;
    }
    for (int i = begin; i < nums.length; ++i) {
        int val = nums[i];
        path.add(val);
        dfs(nums, path, i + 1, k);
        path.remove(path.size() - 1);
    }
}

List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
    Arrays.sort(nums);
    List<Integer> path = new ArrayList<Integer>();
    dfs(nums, path, 0);
    return ans;
}

public void (int[] nums, List<Integer> path, int begin) {
    ans.add(new ArrayList<Integer>(path));
    for (int i = begin; i < nums.length; ++i) {
        int val = nums[i];
        path.add(val);
        dfs(nums, path, i + 1);
        path.remove(path.size() - 1);
    }
}

List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
    if (nums == null || nums.length == 0)
        return ans;
    Arrays.sort(nums);
    List<Integer> path = new ArrayList<Integer>();
    dfs(nums, 0, path);
    return ans;
}
public void (int[] nums, int begin, List<Integer> path) {
    ans.add(new ArrayList<Integer>(path));
    for (int i = begin; i < nums.length; ++i) {
        int val = nums[i];
        path.add(val);
        dfs(nums, i + 1, path);
        path.remove(path.size() - 1);
        while (i + 1 < nums.length && nums[i] == nums[i + 1])
            ++i;
    }
}