# 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()) {
return;
}

for (int i = index; i <= n; 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) {
return;
}

for (int i = index; i < candidates.length; i++) {
if (i > index && candidates[i] == candidates[i-1])  // deal with duplicates
continue;
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) {
return;
}

for (int i = index; i < candidates.length; i++) {
if (i > index && candidates[i] == candidates[i-1])
continue;
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) {
}
return;
}
for (int i = start; i <= n; i++) {
if (n % i == 0) {
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>>();
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));
}
}
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){

for(int i = index; i < s.length; 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)
}
Collections.sort(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>>();
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));
}

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>>();
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);
if (!res.contains(tlist))
}
}
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;
}

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);
}
//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);
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){
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.remove(i + 1);
permute(nums, start + 1, res);
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;
}
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--;
}
}
``````