#include <stdlib.h>
#include <string.h>
typedef struct {
int **rows;
int *colSizes;
int size;
int cap;
} Result;
static int cmp(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (x > y) - (x < y);
}
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(const int *candidates, int n, int idx, int sum,
int target, int *cur, int curSize, Result *res) {
if (sum == target) {
save(res, cur, curSize);
return;
}
if (sum > target || idx == n)
return;
cur[curSize] = candidates[idx];
backtrack(candidates, n, idx + 1, sum + candidates[idx], target, cur,
curSize + 1, res);
int i = idx + 1;
while (i < n && candidates[i] == candidates[idx])
i++;
backtrack(candidates, n, i, sum, target, cur, curSize, res);
}
int **combinationSum2(int *candidates, int candidatesSize, int target,
int *returnSize, int **returnColumnSizes) {
Result res = {0};
qsort(candidates, candidatesSize, sizeof(int), cmp);
int *cur = malloc((candidatesSize ? candidatesSize : 1) * sizeof(int)); // each used at most once
backtrack(candidates, candidatesSize, 0, 0, target, cur, 0, &res);
free(cur);
*returnSize = res.size;
*returnColumnSizes = res.colSizes;
return res.rows;
}
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
vector<vector<int>> result;
vector<int> cur;
sort(candidates.begin(), candidates.end());
backtrack(candidates, 0, 0, target, cur, result);
return result;
}
void backtrack(vector<int> &candidates, int idx, int sum, int &target,
vector<int> &cur, vector<vector<int>> &result) {
if (sum == target) {
result.push_back(cur);
return;
}
if (sum > target || idx == candidates.size())
return;
cur.push_back(candidates[idx]);
backtrack(candidates, idx + 1, sum + candidates[idx], target, cur, result);
cur.pop_back();
int i = idx + 1;
while (i < candidates.size() && candidates[i] == candidates[idx])
i++;
backtrack(candidates, i, sum, target, cur, result);
}
};
package backtracking
import "sort"
func combinationSum2(candidates []int, target int) [][]int {
var result [][]int
var cur []int
sort.Ints(candidates)
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
}
cur = append(cur, candidates[idx])
backtrack(idx+1, sum+candidates[idx])
cur = cur[:len(cur)-1]
i := idx + 1
for i < len(candidates) && candidates[i] == candidates[idx] {
i++
}
backtrack(i, sum)
}
backtrack(0, 0)
return result
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
backtrack(candidates, 0, 0, target, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] candidates, int idx, int sum, int target,
List<Integer> cur, List<List<Integer>> result) {
if (sum == target) {
result.add(new ArrayList<>(cur));
return;
}
if (sum > target || idx == candidates.length) {
return;
}
cur.add(candidates[idx]);
backtrack(candidates, idx + 1, sum + candidates[idx], target, cur, result);
cur.remove(cur.size() - 1);
int i = idx + 1;
while (i < candidates.length && candidates[i] == candidates[idx]) {
i++;
}
backtrack(candidates, i, sum, target, cur, result);
}
}
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function (candidates, target) {
const result = [];
const cur = [];
candidates.sort((a, b) => a - b);
const backtrack = (idx, sum) => {
if (sum === target) {
result.push([...cur]);
return;
}
if (sum > target || idx === candidates.length) return;
cur.push(candidates[idx]);
backtrack(idx + 1, sum + candidates[idx]);
cur.pop();
let i = idx + 1;
while (i < candidates.length && candidates[i] === candidates[idx]) i++;
backtrack(i, sum);
};
backtrack(0, 0);
return result;
};
from typing import List
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
result: List[List[int]] = []
cur: List[int] = []
candidates.sort()
def backtrack(idx: int, total: int) -> None:
if total == target:
result.append(cur[:])
return
if total > target or idx == len(candidates):
return
cur.append(candidates[idx])
backtrack(idx + 1, total + candidates[idx])
cur.pop()
i = idx + 1
while i < len(candidates) and candidates[i] == candidates[idx]:
i += 1
backtrack(i, total)
backtrack(0, 0)
return result
impl Solution {
pub fn combination_sum2(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
let mut result = Vec::new();
let mut cur = Vec::new();
candidates.sort_unstable();
Self::backtrack(&candidates, 0, 0, target, &mut cur, &mut result);
result
}
fn backtrack(
candidates: &[i32],
idx: usize,
sum: i32,
target: i32,
cur: &mut Vec<i32>,
result: &mut Vec<Vec<i32>>,
) {
if sum == target {
result.push(cur.clone());
return;
}
if sum > target || idx == candidates.len() {
return;
}
cur.push(candidates[idx]);
Self::backtrack(candidates, idx + 1, sum + candidates[idx], target, cur, result);
cur.pop();
let mut i = idx + 1;
while i < candidates.len() && candidates[i] == candidates[idx] {
i += 1;
}
Self::backtrack(candidates, i, sum, target, cur, result);
}
}