Sponsored
Sponsored
The primary idea here is to use a backtracking algorithm to explore all potential combinations of numbers that sum up to the target value. By sorting the array first, we can avoid duplicate combinations by skipping over duplicates within the loop. This ensures each combination is unique, as indicated in the problem statement.
Time Complexity: O(2^n) in the worst case, where n is the number of elements in candidates.
Space Complexity: O(n) for recursion stack, where n is the number of elements in the combination.
1#include <stdio.h>
2#include <stdlib.h>
3
4void backtrack(int* candidates, int candidatesSize, int* result, int resultSize, int** returnColumnSizes, int* temp, int tempSize, int target, int startIndex, int* returnSize) {
5 if (target == 0) {
6 (*returnColumnSizes)[*returnSize] = tempSize;
7 result[*returnSize] = malloc(tempSize * sizeof(int));
8 for (int i = 0; i < tempSize; i++) {
9 result[*returnSize][i] = temp[i];
10 }
11 (*returnSize)++;
12 return;
13 }
14 for (int i = startIndex; i < candidatesSize; i++) {
15 if (i > startIndex && candidates[i] == candidates[i-1]) continue;
16 if (candidates[i] > target) break;
17 temp[tempSize] = candidates[i];
18 backtrack(candidates, candidatesSize, result, candidatesSize, returnColumnSizes, temp, tempSize + 1, target - candidates[i], i + 1, returnSize);
19 }
20}
21
22int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
23 qsort(candidates, candidatesSize, sizeof(int), cmpfunc);
24 int** result = malloc(1000 * sizeof(int*));
25 *returnColumnSizes = malloc(1000 * sizeof(int));
26 int temp[1000];
27 *returnSize = 0;
28 backtrack(candidates, candidatesSize, result, candidatesSize, returnColumnSizes, temp, 0, target, 0, returnSize);
29 return result;
30}
31
32int cmpfunc(const void* a, const void* b) {
33 return (*(int*)a - *(int*)b);
34}In this approach, we use a variation of the dynamic programming (DP) paradigm referred to as memoization. Instead of exploring each possibility outright, the DP technique seeks to store the results of previously computed states, allowing reuse and thus reducing redundant calculations. Although it's less intuitive than the backtracking approach, it can provide improved efficiency by leveraging prior knowledge.
This approach may involve defining a recursive function with the current state being a pair of active indices and remaining targets, ensuring we cover all combinations.
Time Complexity: Typically less than O(2^n) due to repeated subproblem optimization.
Space Complexity: Increases due to cache use and recursive call stack.