Combination Sum I II IV

Leave a comment

September 5, 2016 by oneOokay

  • list.contains()
  • new ArrayList(list)
  • Arrays.sort(nums)
  • list.remove(index): list.remove(list.size() – 1)

  • Combination Sum I:
    • 没有重复数; 每个数可以用无数次;所有元素和target都是正数;求所有的unique combinations.
  • Combination Sum II:
    • 有重复的元素; 每个只能用一次;所有元素以及target为正数;找到所有的unique combinations.
  • Combination Sum IV: DP
    • 没有重复元素;每个可以用无数次;所有元素以及target为正数;求一共有多少种可能的combination,不同的排列组合算不同的解.

Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.

用普通的DFS求出所有的解之后返回它的size会Memory Limit Exceeded.而且这里只求解的个数,没有要求求所有的解.

说是一个经典的dp题目,但是我还是有一个很关键的地方不是太明白,跟这个人的问题一样…先放一下吧.

Good solution! But do you know how to get the euqation “comb[target] = sum(comb[target – nums[i]]), where 0 <= i < nums.length, and target >= nums[i]”? Since the one more number can be added to any position into the current combination and make different sequences. I know this will generate a lot of duplicate sequences. But it seems to be not so intuitive to have that equation although I know its correctness.

想明白了…不要想成是把nums[i]加到前面的所有的comb(target – nums[i])里面,从comb(0)开始逐渐往里加nums[i]而形成的最终comb(target);而事实上其实是从target开始,在array中loop through每一个nums[i], loop一个就代表了从target开始往0走了第一步,这个第一步可以为nums[i]中的任何一个数子;继续往下的话就继续找nums[i]组成各种可能的情况.所以这个是从targetDFS深入往回走的过程,一直走到了comb(0)这里,得到一个已知的解,然后逐渐trace back up build up 所有的comb来得到最终的comb(target).这样其实就保证了所有解的可能性.这个其实就是和爬楼梯是一样的.

以及下面提到的两种方法虽然一种所谓的Top-down/bottom-up其实只是相对于comb(i)的i的值来说的.

总之呢,动态转移方式是: comb(target) = SUM(comb(target – nums[i])) i : [0, nums.length – 1].

comb(target)等于所有的comb(target – nums[i])的值的和.

[1,2,3] target = 4.
comb(4) = comb ( 4 - nums[2]) + comb( 4 - nums[1]) + comb( 4 - nums[0])
= comb(1) + comb(2) + comb(3)
comb(0) = 0

看了眼总的来说DP有两种方法Top-down和bottom-up.以及一个HashMap的版本.

//DP: Top-down: Target Recursion深入慢慢减到0之后开始build up array dp[]
这个比bottom up更快,因为求的所有的dp[i]都是存在可能性的dp
public int combinationSum4(int[] nums, int target) {
 if (nums == null || nums.length == 0) return 0;
 int[] dp = new int[target + 1];
 Arrays.fill(dp, -1);
 dp[0] = 1;
 return helper(dp, target, nums);
 }
 private int helper(int[] dp, int target, int[] nums){
 if (dp[target] != -1) return dp[target];
 int ans = 0;
 for (int i = 0; i < nums.length; i ++){  if (target - nums[i] >= 0){
 ans += helper(dp, target - nums[i], nums);
 }}
 dp[target] = ans;
 return ans;
 }

//DP: Bottom-Up:从1开始build up dp[]一直到dp[target]
核心思想依旧是那个动态转移方程
public int combinationSum4(int[] nums, int target) {
 int[] dp = new int[target + 1];
 dp[0] = 1;
 for(int i = 1; i <= target; i ++){
 for (int j = 0; j < nums.length; j ++){  if (i - nums[j] >= 0){
 dp[i] += dp[i - nums[j]];
 } } }
 return dp[target];
 }

//用HashMap代替了dp int array
public int combinationSum4(int[] nums, int target) {
 HashMap<Integer, Integer> map = new HashMap<>();
 map.put(0, 1);
 return helper(map, nums, target);
 }
 
 private int helper(HashMap<Integer, Integer> map, int[] nums, int target){
 if (map.containsKey(target)) return map.get(target);
 int res = 0;
 for (int i = 0; i < nums.length; i ++){  if (target - nums[i] >= 0){
 res += helper(map, nums, target - nums[i]);
 }
 }
 map.put(target, res);
 return res;
 }


Combination Sum I

  • Array: 没有重复数; 每个数可以用无数次;所有元素和target都是正数;找到unique combinations.

Given a set of candidate numbers (C) (without duplicates) 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]
]

时间复杂度是?

  • 不需要Sort Array:因为没有重复的值存在.
  • helper method传入index, list, ans, nums 和 target
  • 把list加入ans的条件是target == 0;如果target < 0,直接返回。
  • for loop每次从i = index开始
    • 把nums[i]加入到list中
    • call helper method: 传入i (不需要i+1因为同一个元素可以取无限次)和target – nums[i].
    • 从list中移除刚加入的元素

Combination Sum II

  • Array里面有重复的元素; 每个元素只能用一次;所有元素以及target为正数;找到unique combinations.

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

  • Sort Array:因为含有重复的值,排序之后进行除重
  • 除重技巧:
    • for (int i = index; i < nums.length; i ++)
    • if (i > index && nums[i] == nums[i – 1]) continue;
    • 这里是要i大于index而不是i > 0. (如果是i>0的话那么就需要一个boolean visited[],这里没有必要)
    • i大于 i的初始值 是如何进行除重的?
      • 在同一个helper method里面,每一次for loop都是加入一个元素然后进入下一层recursion,出来之后移除掉当前,再进入下一个forloop加下一个元素.
      • 所以相当于当i > i的初始值 的时候,每一次把元素加入到list里面,这个元素之前的数字都是不在list里面的.
      • 这里就会存在重复:前一个数字和当前数字相同,前面的已经处理过了,把前一个数字移掉了,轮到现在这个数,把它加到list里面的话,就完全是和之前的相同了,所以要跳!过!它!
      • 那么是如何把重复的元素加入到list里面的?
      • 当前helper recursion i = index; helper(index + 1).
      • 所以是在下一层helper recursion(index + 1) for loop第一次循环的时候,把第二个重复的元素加入到了list里面.

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

%d bloggers like this: