Classic Interview 150 Questions P39 Combination Sum

---

Timeline

Timeline

2025-11-29

init

---

Problem:

P39 Combination Sum

https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-interview-150

Backtracking, note the start. Since numbers can be reused, use i as the next start in the backtrack call.

#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    private:
	vector<vector<int> > res;
	void backtrace(vector<int> &path, vector<int> &candidates, int start, int target)
	{
		if (target == 0) {
			res.push_back(path);
			return;
		} else if (target < 0) {
			return;
		}

		for (int i = start; i < candidates.size(); i++) {
			if (candidates[i] > target) { //Pruning
				break;
			}
			path.push_back(candidates[i]);
			// Go to the next level
			backtrace(path, candidates, i, target - candidates[i]);
			path.pop_back();
		}
	}

    public:
	vector<vector<int> > combinationSum(vector<int> &candidates, int target)
	{
		vector<int> path;
		std::sort(candidates.begin(), candidates.end());
		backtrace(path, candidates, 0, target);
		return res;
	}
};

leetcode hot 100 rewrite

#include <vector>

using std::vector;

class Solution {
    private:
        void __combinationSum(vector<int> &candidates, int target, vector<vector<int> > &res,
                              vector<int> &curr, int curr_sum, int pos)
        {
                if (curr_sum == target) {
                        res.push_back(curr);
                        return;
                } else if (curr_sum > target) {
                        return;
                }

                int i, n = candidates.size();
                for (i = pos; i < n; i++) {
                        curr.push_back(candidates[i]);
                        curr_sum += candidates[i];

                        __combinationSum(candidates, target, res, curr, curr_sum, i);

                        curr_sum -= candidates[i];
                        curr.pop_back();
                }
        }

    public:
        vector<vector<int> > combinationSum(vector<int> &candidates, int target)
        {
                vector<vector<int> > res;
                vector<int> curr;
                __combinationSum(candidates, target, res, curr, 0, 0);

                return res;
        }
};