Subsets I/II, Permutations I/II,Combinations I/II/III

Subset I
Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        backtracking(nums, res, new ArrayList<Integer>(), 0);
        return res;
    }

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

Subsets II, 可能有重复

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        backtracking(nums, new ArrayList<Integer>(), res, 0);
        return res;
    }

    public void backtracking(int[] nums, List<Integer> list,  List<List<Integer>> res, int start) {
        res.add(list);
        res.add(new ArrayList<Integer>(list));
        for (int i = start; i < nums.length; i++) {
            if (i != start && nums[i-1] == nums[i]) continue; // skip duplicates
            list.add(nums[i]);
            backtracking(nums, list, res, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

46. Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

public class Solution {
public List<List> permute(int[] nums) {
List<List> res = new ArrayList<List>();
if (nums == null || nums.length == 0) return res;
helper(res, nums, new ArrayList());
return res;
}
public void helper (List<List> res, int[] nums, List list) {

    if (list.size() == nums.length) {
        if (!res.contains(list)) {
            res.add(new ArrayList(list));
        }
        return;
    }
    for (int i = 0; i &lt; nums.length; i++) {
        if (list.contains(nums[i])) continue;
        list.add(nums[i]);
        helper(res, nums, list);
        list.remove(list.size() - 1);
    }
}

}

<br />Permutation II, 可能出现重复元素

public class Solution {
public List<List> permuteUnique(int[] nums) {
List<List> res = new ArrayList<List>();
if (nums == null || nums.length == 0) return res;
Arrays.sort(nums);
int size = nums.length;
boolean[] used = new boolean[size];
backtracking(res, new ArrayList(), nums, used);
return res;
}

public void backtracking(List&lt;List&gt; res, List list, int[] nums, boolean[] used) {
    if (list.size() == nums.length) {
        res.add(new ArrayList(list));
        return;    
    }
    for (int i = 0; i &lt; nums.length; i++) {
        if (used[i] || (i != 0 &amp;&amp; !used[i - 1] &amp;&amp; nums[i - 1] == nums[i] )) continue;
        list.add(nums[i]);
        used[i] = true;
        backtracking(res, list, nums, used);
        list.remove(list.size() - 1);
        used[i] = false;
    }
}

}

<br />77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

<br />解法: 

public class Solution {
public List<List> combine(int n, int k) {
List<List> res = new ArrayList();
if (n <= 0 || k n) return res;
int[] nums = new int[n];
for (int i = 0; i < nums.length; i++) {
nums[i] = i + 1;
}
backtracking(nums, new ArrayList(), res, 0, k);
return res;
}

public void backtracking(int[] nums, List list, List&lt;List&gt; res, int start, int k) {
    if (list.size() == k) {
        res.add(new ArrayList(list));
    }
    for (int i = start; i &lt; nums.length; i++) {
        list.add(nums[i]);
        backtracking(nums, list, res, i + 1, k);
        list.remove(list.size() - 1);
    }
}

}

<br />39. Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 
[
  [7],
  [2, 2, 3]
]

public class Solution {
public List<List> combinationSum(int[] candidates, int target) {
List<List> res = new ArrayList();
if (candidates == null || candidates.length == 0 || target < 0 ) return res;
Arrays.sort(candidates);
backtracking(candidates, target, res, new ArrayList(), 0);
return res;
}

public void backtracking(int[] candidates, int target, List&lt;List&gt; res, List list, int start) {
   if (target &lt; 0) return;    
   if (target == 0) {
       res.add(new ArrayList(list));
   }
   for (int i = start; i &lt; candidates.length; i++) {
       list.add(candidates[i]);
       backtracking(candidates, target - candidates[i], res, list, i);
       list.remove(list.size() - 1);
   }
}

}

<br />Combination Sum II
Each number in C may only be used once in the combination.


public class Solution {
public List<List> combinationSum2(int[] candidates, int target) {
List<List> res = new ArrayList();
if (candidates == null || candidates.length == 0 || target < 0) return res;
Arrays.sort(candidates);
backtracking(candidates, target, 0, res, new ArrayList());
return res;
}
public void backtracking(int[] candidates, int target, int start, List<List> res, List list) {
if (target < 0) return;
if (target == 0) {
res.add(new ArrayList(list));
return;
}
for (int i = start; i < candidates.length; i++ ) {
if (i != start && candidates[i] == candidates[i – 1]) continue;
list.add(candidates[i]);
backtracking(candidates, target – candidates[i], i + 1, res, list);
list.remove(list.size() – 1);
}
}
}

<br />216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.


Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

public class Solution {
public List<List> combinationSum3(int k, int n) {
List<List> res = new ArrayList();
if (k < 1 || n <= 0) return res;
backtracking(k, n, res, new ArrayList(), 1);
return res;
}

public void backtracking(int k, int target, List&lt;List&gt; res, List list, int start) {
    if (target &lt; 0) return;
    if (target == 0 &amp;&amp; list.size() == k) {
        res.add(new ArrayList(list));
        return;
    }
    for (int i = start; i &lt;= 9; i++) {
        list.add(i);
        backtracking(k, target - i, res, list, i + 1);
        list.remove(list.size() - 1);
    }
}

}
“`

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s