Combination/Permutation/Subset

Part I: Combination

1. k numbers from 1 to n

public List combine(int n, int k) { List res = new ArrayList(); 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 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); } }

1. Combination sum: element can be repeately used

public List combinationSum(int[] candidates, int target) { List res = new ArrayList(); 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 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); } }

1. Combination sum: element can be used once

public List combinationSum2(int[] candidates, int target) { List res = new ArrayList(); 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 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); } }

1. Factor combinations

public List getFactors(int n) { List ret = new ArrayList (); helper(ret, new ArrayList<Integer> (), n, 2); return ret; } private void helper(List 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 subsets(int[] nums) { List res = new ArrayList(); 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 subsets(int[] S) { List result = new ArrayList(); 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 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 subsets(int[] nums) { int n = nums.length; List 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 subsetsWithDup(int[] nums) { List res = new ArrayList(); 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 subsetsWithDup(int[] nums) { List res = new ArrayList(); 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 tmp = new ArrayList(); 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 permute(int[] nums) { List res = new ArrayList(); 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 bak = new ArrayList(); 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 permuteUnique(int[] nums) { List res = new ArrayList(); 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 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(); }

1. next permutation

public void nextPermutation(int[] nums) { if(nums == null || nums.length<2) return;="" int="" p="0;" for(int="" i="nums.length-2;">=0; i--){ if(nums[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--; } }