[LeetCode]Combination Sum题解(DFS)

Combination Sum

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]

]

用类似于dfs的思想来解题。

数组从头到尾，每次决定是否将当前的值加入组合：

如果是，那么判断当前组合是否sum == target，
- 等于——>将该组合加入解集合，return；
- 不等于——>继续递归
如果不是，那么index+1（数组向后移动），继续递归

代码非常容易理解，如下所示：

class Solution {

public:

    vector<vector<int>> re;

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

        vector<int> temp;

        search(candidates,temp,0,candidates.size(),target,0);

        return re;

    }

    void search(vector<int> candidates,vector<int> temp,int index,int len,int target,int cur){

        if(index >= len || cur > target) return;

        //do not select this value,search deepper，index need increase

        search(candidates,temp,index+1,len,target,cur);

        /*

        * select this value,and judge if it equals the target.

        * If yes,push back the vector and return,if not,search continue

        * index don't change,because the number can be repeated

        */

        temp.push_back(candidates[index]);

        cur += candidates[index];

        if(cur == target){

            re.push_back(temp);

            return;

        }

        else{

            search(candidates,temp,index,len,target,cur);

        }

    }

};

巴特西

[LeetCode]Combination Sum题解(DFS)

最新文章

热门文章