39. Combination Sum

Leetcode Array Backtracking

题目

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

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

Note:

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

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

分析

典型的backtracking类型题目。关键是输出后的结果会有重复。使用set能将重复的结果剔除。

#include <algorithm>

class Solution {
public:

    void combinationSumHelper(vector<int>& candidates, int target, set<vector<int>>& result, vector<int> &chosen){

        if (target == 0){
        // base case
            vector<int> chosen_sorted(chosen.begin(), chosen.end());
            sort(chosen_sorted.begin(), chosen_sorted.end());
            result.insert(chosen_sorted);

        }else{
            for (vector<int>::iterator iter=candidates.begin(); iter!=candidates.end(); iter++){
                if (target>=*iter){
                    //choose
                    int s = *iter;
                    chosen.push_back(s);

                    //explore
                    combinationSumHelper(candidates, target-s, result, chosen);

                    //unchoose
                    chosen.pop_back();
                }
            }
        }

    }


    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

        set<vector<int>> result;
        vector<int> chosen;
        combinationSumHelper(candidates, target, result, chosen);
        vector<vector<int>> finals(result.begin(), result.end());
        return finals;
    }
};

但其实还有更简单的方法：

采用回溯法。由于组合中的数字要按序排列，我们先将集合中的数排序。依次把数字放入组合中，因为所有数都是正数，如果当前和已经超出目标值，则放弃；如果和为目标值，则加入结果集；如果和小于目标值，则继续增加元素。由于结果集中不允许出现重复的组合，所以增加元素时只增加当前元素及之后的元素。

#include <algorithm>

class Solution {
public:

    void combinationSumHelper(vector<int>& candidates, int target, vector<vector<int>>& res, vector<int> &chosen, int position){

        if (target == 0){
        // base case
            res.push_back(chosen);

        }else{
            for (int i=position; (i<candidates.size()) && (candidates[i]<= target); i++ ){
                //choose
                chosen.push_back(candidates[i]);

                //explore
                combinationSumHelper(candidates, target-candidates[i], res, chosen, i);

                //unchoose
                chosen.pop_back();
            }
        }
    }


    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

        vector<vector<int>> res;
        vector<int> chosen;
        sort(candidates.begin(), candidates.end());
        combinationSumHelper(candidates, target, res, chosen, 0);
        return res;
    }
};

题目难点在于重复的处理和排序。