#include <stdlib.h>
#include <string.h>
typedef struct {
int **rows;
int *colSizes;
int size;
int cap;
} Result;
static void save(Result *res, const int *cur, int curSize) {
if (res->size == res->cap) {
res->cap = res->cap ? 2 * res->cap : 16;
res->rows = realloc(res->rows, res->cap * sizeof(int *));
res->colSizes = realloc(res->colSizes, res->cap * sizeof(int));
}
res->rows[res->size] = malloc(curSize * sizeof(int));
memcpy(res->rows[res->size], cur, curSize * sizeof(int));
res->colSizes[res->size++] = curSize;
}
static void backtrack(Result *res, int *cur, int curSize, int idx,
const int *candidates, int n, int target, int sum) {
if (sum == target) {
save(res, cur, curSize);
return;
}
if (sum > target || idx >= n)
return;
// include candidates[idx], stay on idx (can reuse it)
cur[curSize] = candidates[idx];
backtrack(res, cur, curSize + 1, idx, candidates, n, target,
sum + candidates[idx]);
// skip candidates[idx] for good, move on
backtrack(res, cur, curSize, idx + 1, candidates, n, target, sum);
}
int **combinationSum(int *candidates, int candidatesSize, int target,
int *returnSize, int **returnColumnSizes) {
Result res = {0};
int *cur = malloc(target * sizeof(int)); // candidates >= 1, so depth <= target
backtrack(&res, cur, 0, 0, candidates, candidatesSize, target, 0);
free(cur);
*returnSize = res.size;
*returnColumnSizes = res.colSizes;
return res.rows;
}
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
vector<vector<int>> result;
vector<int> cur;
backtrack(result, cur, 0, candidates, target, 0);
return result;
}
void backtrack(vector<vector<int>> &result, vector<int> &cur, int idx,
vector<int> &candidates, int target, int sum) {
if (sum == target) {
result.push_back(cur);
return;
}
if (sum > target || idx >= candidates.size())
return;
// include candidates[idx], stay on idx (can reuse it)
cur.push_back(candidates[idx]);
backtrack(result, cur, idx, candidates, target, sum + candidates[idx]);
cur.pop_back();
// skip candidates[idx] for good, move on
backtrack(result, cur, idx + 1, candidates, target, sum);
}
};
package backtracking
func combinationSum(candidates []int, target int) [][]int {
var result [][]int
var cur []int
var backtrack func(idx, sum int)
backtrack = func(idx, sum int) {
if sum == target {
result = append(result, append([]int(nil), cur...))
return
}
if sum > target || idx >= len(candidates) {
return
}
// include candidates[idx], stay on idx (can reuse it)
cur = append(cur, candidates[idx])
backtrack(idx, sum+candidates[idx])
cur = cur[:len(cur)-1]
// skip candidates[idx] for good, move on
backtrack(idx+1, sum)
}
backtrack(0, 0)
return result
}
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), 0, candidates, target, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> cur, int idx,
int[] candidates, int target, int sum) {
if (sum == target) {
result.add(new ArrayList<>(cur));
return;
}
if (sum > target || idx >= candidates.length) {
return;
}
// include candidates[idx], stay on idx (can reuse it)
cur.add(candidates[idx]);
backtrack(result, cur, idx, candidates, target, sum + candidates[idx]);
cur.remove(cur.size() - 1);
// skip candidates[idx] for good, move on
backtrack(result, cur, idx + 1, candidates, target, sum);
}
}
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
const result = [];
const cur = [];
const backtrack = (idx, sum) => {
if (sum === target) {
result.push([...cur]);
return;
}
if (sum > target || idx >= candidates.length) return;
// include candidates[idx], stay on idx (can reuse it)
cur.push(candidates[idx]);
backtrack(idx, sum + candidates[idx]);
cur.pop();
// skip candidates[idx] for good, move on
backtrack(idx + 1, sum);
};
backtrack(0, 0);
return result;
};
from typing import List
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result: List[List[int]] = []
cur: List[int] = []
def backtrack(idx: int, total: int) -> None:
if total == target:
result.append(cur[:])
return
if total > target or idx >= len(candidates):
return
# include candidates[idx], stay on idx (can reuse it)
cur.append(candidates[idx])
backtrack(idx, total + candidates[idx])
cur.pop()
# skip candidates[idx] for good, move on
backtrack(idx + 1, total)
backtrack(0, 0)
return result
impl Solution {
pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
let mut result = Vec::new();
let mut cur = Vec::new();
Self::backtrack(&mut result, &mut cur, 0, &candidates, target, 0);
result
}
fn backtrack(
result: &mut Vec<Vec<i32>>,
cur: &mut Vec<i32>,
idx: usize,
candidates: &[i32],
target: i32,
sum: i32,
) {
if sum == target {
result.push(cur.clone());
return;
}
if sum > target || idx >= candidates.len() {
return;
}
// include candidates[idx], stay on idx (can reuse it)
cur.push(candidates[idx]);
Self::backtrack(result, cur, idx, candidates, target, sum + candidates[idx]);
cur.pop();
// skip candidates[idx] for good, move on
Self::backtrack(result, cur, idx + 1, candidates, target, sum);
}
}