LeetCode: Combination Sum II

题目

https://oj.leetcode.com/problems/combination-sum-ii/

分析

这道题是Combination Sum的变形,也是采用DFS的思路,但相比之下要注意两点:

  1. 因为不能重复,所以在进进行DFS递归时,要直接从当前位置的下一个位置开始进行“试探”。

  2. 若num中存在两个相同的元素,为了防止结果中重复出现,只有在第一个元素被选中的情况下,第二个元素才进行“试探”,否则不进行“试探”。

代码

class Solution
{
public:
    vector<vector<int>> combinationSum2(vector<int> &num, int target)
    {
        vector<int> solution;
        this->num = num;
        sort(this->num.begin(), this->num.end());

        DFS(solution, target, 0);

        return res;
    }

    void DFS(vector<int> &solution, int target, int start)
    {
        if (target == 0)
        {
            res.push_back(solution);
        }
        else
        {
            for (int i = start; i < num.size() && num[i] <= target; i++)
            {
                if (i > 0 && num[i] == num[i-1] && num[i-1] != solution.back())
                    continue;
                solution.push_back(num[i]);
                DFS(solution, target - num[i], i + 1);
                solution.pop_back();
            }
        }
    }

private:
    vector<int> num;
    vector<vector<int>> res;
};

参考

http://blog.csdn.net/timberwolf_2012/article/details/40479161

http://www.cnblogs.com/remlostime/archive/2012/10/29/2745125.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40509643