Combination Sum I II III

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.
    • 先sort. 在helper method里面什么时候进行target的判断. 在for – loop里面.
    • 注意什么时候return什么时候continue
  • Combination Sum II:
    • 有重复的元素; 每个只能用一次;所有元素以及target为正数;找到所有的unique combinations.
    • 不用boolean[] visited的除重方法
    • 注意什么时候return什么时候continue
  • Combination Sum III:
    • 1 – 9, 求k个元素加起来==n的集合,不能取重复元素
  • Combination Sum IV: DP
    • 没有重复元素;每个可以用无数次;所有元素以及target为正数;求一共有多少种可能的combination,不同的排列组合算不同的解.

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? 非必要.这里sort和不sort的写法不一样.sort更加高效.
    • 这里可以看一下加入list的条件在for loop内和在helper method开始的区别
  • 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中移除刚加入的元素
    public List combinationSum(int[] candidates, int target) {
        List res = new ArrayList<>();
        if (candidates == null || candidates.length == 0) 
            return res;
        Arrays.sort(candidates);
        helper(candidates, new ArrayList(), res, target, 0);
        return res;
    }
    //sort的helper method.
    private void helper(int[] nums, List list, List res, int target, int index){
        for (int i = index; i < nums.length; i ++){
//发现加入当前nums[i]总和已经超过target了,此时就可以返回了,不需要继续.
            if (target - nums[i] < 0) 
                return;
//同样的发现加入当前nums[i]已经达到target,也可以返回,不需要继续.
            if (target - nums[i] == 0){
                list.add(nums[i]);
                res.add(new ArrayList(list));
                list.remove(list.size() - 1);
                return;
            }
//这里只有在target>0的情况下才继续搜搜索
            list.add(nums[i]);
            helper(nums, list, res, target - nums[i], i);
            list.remove(list.size() - 1);
        }   
    }
//没有sort的method.因为并不知道后一个元素是大还是小
//(如果有负数的话,所以对每一个元素都要搜索)这样比上面的算法多了搜索的次数.
    private void helper(int[] nums, List list, List res, int target, int index){
        if (target < 0) return;
        if (target == 0){
            res.add(new ArrayList(list));
            return;
        }
        for (int i = index; i < nums.length; i ++){            
            list.add(nums[i]);
            helper(nums, list, res, target - nums[i], i);
            list.remove(list.size() - 1);
        }   
    }

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里面.
    public List combinationSum2(int[] candidates, int target) {
        List res = new ArrayList<>();
        if (candidates == null || candidates.length == 0)
            return res;
        Arrays.sort(candidates);
        boolean[] visited = new boolean[candidates.length];;
        helper(candidates, new ArrayList(), res, target, 0);
        return res;
    }
    
    private void helper(int[] nums, List list, List res, int target, int index){
        for (int i = index; i < nums.length; i ++){              if (i > index && nums[i] == nums[i - 1])
                continue;
            if (target - nums[i] < 0) 
                return;
            if (target - nums[i] == 0){
                list.add(nums[i]);
                res.add(new ArrayList(list));
                list.remove(list.size() - 1);
                return;
            }
            list.add(nums[i]);
            helper(nums, list, res, target - nums[i], i + 1);
            list.remove(list.size() - 1);
        }
    }

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 List<List> combinationSum3(int k, int n) {
        List<List> res = new ArrayList<>();
        if (k == 0 || n < 1) 
            return res;
        helper(1, new ArrayList(), res, n, k);
        return res;
    }
    
    private void helper(int num, List list, List<List> res, int target, int k){
        for (int i = num; i <= 9; i ++){
            if (target - i < 0)
                  return;
             if (target - i == 0 && list.size() == k - 1){
                 list.add(i);
                 res.add(new ArrayList(list));
                 list.remove(list.size() - 1);
                 return;             }
             if (target - i > 0 && list.size() >= k - 1)
                continue;
            list.add(i);
            helper(i + 1, list, res, target - i, k);
            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

%d bloggers like this: