Combination/Permutation/Subset

Part I: Combination

1. k numbers from 1 to n

   public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (n < 1 || k > n) {
            return res;
        }
        combine(n, 1, new ArrayList<Integer>(), k, res);
        return res;
    }
   
    public void combine(int n, int index, List<Integer> list, int k, List<List<Integer>> res) {
        if (index > n && k != list.size()) {
            return;
        }
        if (k == list.size()) {
            res.add(new ArrayList<>(list));
            return;
        }
   
        for (int i = index; i <= n; i++) {
            list.add(i);
            combine(n, i+1, list, k, res);
            list.remove(list.size()-1);
        }
    }
   

2. Combination sum: element can be repeately used

   public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();   
        if (candidates.length == 0) {
            return res;
        }
        Arrays.sort(candidates);
        combineSum(candidates, 0, target, new ArrayList<Integer>(), res);
        return res;
    }
   
    public void combineSum(int[] candidates, int index, int target, List<Integer> curr,  List<List<Integer>> res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<Integer>(curr));
            return;
        }
   
        for (int i = index; i < candidates.length; i++) {
            if (i > index && candidates[i] == candidates[i-1])  // deal with duplicates
                continue;
            curr.add(candidates[i]);
            combineSum(candidates, i, target-candidates[i], curr, res);
            curr.remove(curr.size()-1);
        }
    }
   

3. Combination sum: element can be used once

   public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();   
        if (candidates.length == 0) {
            return res;
        }
        Arrays.sort(candidates);
        combineSum(candidates, 0, target, new ArrayList<Integer>(), res);
        return res;
    }
   
    public void combineSum(int[] candidates, int index, int target, List<Integer> curr,  List<List<Integer>> res) {
        if (index > candidates.length || target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<Integer>(curr));
            return;
        }
   
        for (int i = index; i < candidates.length; i++) {
            if (i > index && candidates[i] == candidates[i-1])
                continue;
            curr.add(candidates[i]);
            combineSum(candidates, i+1, target-candidates[i], curr, res);
            curr.remove(curr.size()-1);
        }
    }
   

4. Factor combinations

   public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> ret = new ArrayList<List<Integer>> ();
        helper(ret, new ArrayList<Integer> (), n, 2);
        return ret;
    }
   
    private void helper(List<List<Integer>> ret, List<Integer> item, int n, int start) {
        if (n == 1) {
            if (item.size() > 1) {
                ret.add(new ArrayList<Integer> (item));
            }
            return;
        }
        for (int i = start; i <= n; i++) {
            if (n % i == 0) {
                item.add(i);
                helper(ret, item, n/i, i);
                item.remove(item.size()-1);
            }
        }
    }
   

Part II: Subsets

1. distinct elements

a. insert element to the previous result

public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>());
        if (nums.length == 0) {
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int size = res.size();

            for (int j = 0; j < size; j++) {
                List<Integer> tlist = new ArrayList<>(res.get(j));
                tlist.add(num);
                res.add(tlist);
            }
        }
        return res;
    }

b. DFS

public List<List<Integer>> subsets(int[] S) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();

    if(S.length == 0){
        return result;
    }

    Arrays.sort(S);
    dfs(S, 0, new ArrayList<Integer>(), result);
    return result;
}

public void dfs(int[] s, int index, List<Integer> path, List<List<Integer>> result){
    result.add(new ArrayList<Integer>(path));

    for(int i = index; i < s.length; i++){
        path.add(s[i]);
        dfs(s, i+1, path, result);
        path.remove(path.size()-1);
    }
}

c.bit manipulation

public List<List<Integer>> subsets(int[] nums) {
    int n = nums.length;
    List<List<Integer>> subsets = new ArrayList<>();
    for (int i = 0; i < Math.pow(2, n); i++)
    {
        List<Integer> subset = new ArrayList<>();
        for (int j = 0; j < n; j++)
        {
            if (((1 << j) & i) != 0)
                subset.add(nums[j]);
        }
        Collections.sort(subset);
        subsets.add(subset);
    }
    return subsets;
}

1. with duplicate elements

a. when encounter duplicate, add new element only to the right half: see the variable start

public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>());
        if (nums.length == 0) {
            return res;
        }
        Arrays.sort(nums);
        int start = 0;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int size = res.size();

            for (int j = start; j < size; j++) {
                List<Integer> tlist = new ArrayList<>(res.get(j));
                tlist.add(num);
                res.add(tlist);
            }

            start = 0;
            if (i < nums.length-1 && nums[i] == nums[i+1]) {
                start = size;
            }

        }
        return res;
    }

b. check if the list is already in the result each time, less efficient

public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>());
        if (nums.length == 0) {
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {

            int num = nums[i];
            List<List<Integer>> tmp = new ArrayList<List<Integer>>();
            for (List<Integer> list : res) {
                List<Integer> tlist = new ArrayList<>(list);
                tlist.add(num);
                if (!res.contains(tlist))
                    tmp.add(tlist);
            }
            res.addAll(tmp);
        }
        return res;
    }

Part III: Permutations

1. Distinct elements

a. add new element to every possible position of the previous set

public List<List<Integer>> permute(int[] nums) {
         List<List<Integer>> res = new ArrayList<List<Integer>>();
         if (nums.length == 0) {
             return res;
         }

        res.add(new ArrayList<Integer>());

         for (int i = 0; i < nums.length; i++) {
             int num = nums[i];
             int size = res.size();

             List<List<Integer>> bak = new ArrayList<List<Integer>>();

             for (int j = 0; j < size; j++) {
                 List<Integer> list = res.get(j);
                 for (int k = 0; k <= list.size(); k++) {
                     List<Integer> tmp = new ArrayList<>(list);
                     tmp.add(k, num);
                     bak.add(tmp);
                 }
                 //res.remove(j);
             }
             res = bak;
         }
         return res;
    }

b. swap every element once to the front and do the same thing for the rest

public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int num : nums) list.add(num);
        permute(list, 0, res);
        return res;
    }
    private void permute(LinkedList<Integer> nums, int start, List<List<Integer>> res){
        if (start == nums.size() - 1){
            res.add(new LinkedList<Integer>(nums));
            return;
        }
        for (int i = start; i < nums.size(); i++){
            if (i > start && nums.get(i) == nums.get(i - 1)) continue; // this deal with duplicates
            nums.add(start, nums.get(i));
            nums.remove(i + 1);
            permute(nums, start + 1, res);
            nums.add(i + 1, nums.get(start));
            nums.remove(start);
        }
    }

1. with duplicates: check previous code

2. find the kth permutation sequence of number 1 to n

   public String getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) {
            return new String();
        }    
   
        List<Integer> nums = new ArrayList<>();
        int fac = 1;
        for (int i = 1; i <= n; i++) {
            fac *= i;
            nums.add(i);
        }
        if (k > fac) {
            return new String();
        }
        fac /= n;
        k--;
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            int index = k / fac;
            //if (index > 0)
                //index--;
            sb.append(nums.get(index));
            nums.remove(index);
            k = k % fac;
            if (i < n)
                fac /= n - i;
        }
        return sb.toString();
    }
   

3. next permutation

public void nextPermutation(int[] nums) {
    if(nums == null || nums.length<2)
        return;

    int p=0;            
    for(int i=nums.length-2; i>=0; i--){
        if(nums[i]<nums[i+1]){
            p=i;
            break;
        }    
    }

    int q = 0;
    for(int i=nums.length-1; i>p; i--){
        if(nums[i]> nums[p]){
            q=i;
            break;
        }    
    }

    if(p==0 && q==0){
        reverse(nums, 0, nums.length-1);
        return;
    }

    int temp=nums[p];
    nums[p]=nums[q];
    nums[q]=temp;

    if(p<nums.length-1){
        reverse(nums, p+1, nums.length-1);
    }
}

public void reverse(int[] nums, int left, int right){
    while(left<right){
        int temp = nums[left];
        nums[left]=nums[right];
        nums[right]=temp;
        left++;
        right--;
    }
}