diff options
author | Jack Sangdahl <[email protected]> | 2024-08-13 01:26:24 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-13 01:26:24 -0600 |
commit | f2d3cef7086d326f38224db98dd95f0b1fef6ebc (patch) | |
tree | eef74debe471188a8d1569d52ce076516511e4d7 | |
parent | 484e384acfe8544836814d1a0e044c15caa36768 (diff) | |
download | leetcode-f2d3cef7086d326f38224db98dd95f0b1fef6ebc.tar.gz leetcode-f2d3cef7086d326f38224db98dd95f0b1fef6ebc.zip |
40. combination sum 2
-rw-r--r-- | combination_sum2.c | 60 | ||||
-rw-r--r-- | combination_sum2.py | 37 |
2 files changed, 97 insertions, 0 deletions
diff --git a/combination_sum2.c b/combination_sum2.c new file mode 100644 index 0000000..6d20d09 --- /dev/null +++ b/combination_sum2.c @@ -0,0 +1,60 @@ +// 40. Combination Sum II +#include "leetcode.h" + +/* + * given a collection of candidate numbers and a target number, find all unique + * combinations in 'candidates' where the candidate numbers sum to 'target'. + * each number in 'candidates' may only be used once + */ + +int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } + +void dfs(int *candidates, int candidatesSize, int target, int idx, int *curr, + int currSize, int *returnSize, int **returnColumnSizes, int ***res) { + int prev = 0; + for (int i = idx; i < candidatesSize; i++) { + if (candidates[i] == target) { + (*returnSize)++; + *res = (int **)realloc(*res, (*returnSize) * sizeof(int *)); + (*res)[(*returnSize) - 1] = (int *)malloc((currSize + 1) * sizeof(int)); + memcpy((*res)[(*returnSize) - 1], curr, currSize * sizeof(int)); + (*res)[(*returnSize) - 1][currSize] = candidates[i]; + (*returnColumnSizes) = + (int *)realloc((*returnColumnSizes), (*returnSize) * sizeof(int)); + (*returnColumnSizes)[(*returnSize) - 1] = currSize + 1; + break; + } else if (candidates[i] <= (target / 2) && candidates[i] != prev) { + curr[currSize] = candidates[i]; + dfs(candidates, candidatesSize, target - candidates[i], i + 1, curr, + currSize + 1, returnSize, returnColumnSizes, res); + prev = candidates[i]; + } else if (candidates[i] > target) + break; + } +} + +int **combinationSum2(int *candidates, int candidatesSize, int target, + int *returnSize, int **returnColumnSizes) { + qsort(candidates, candidatesSize, sizeof(int), cmp); + int *curr = (int *)malloc(100 * sizeof(int)), currSize = 0; + int **ans = (int **)malloc(sizeof(int *)); + (*returnColumnSizes) = (int *)malloc(sizeof(int)); + (*returnSize) = 0; + dfs(candidates, candidatesSize, target, 0, curr, currSize, returnSize, + returnColumnSizes, &ans); + free(curr); + return ans; +} + +int main() { + int c1[] = {10, 1, 2, 7, 6, 1, 5}, c2[] = {2, 5, 2, 1, 2}, rs1, rs2; + int *rcs1 = (int *)malloc(ARRAY_SIZE(c1) * sizeof(int)); + int *rcs2 = (int *)malloc(ARRAY_SIZE(c2) * sizeof(int)); + int **cs21 = combinationSum2(c1, ARRAY_SIZE(c1), 8, &rs1, (int **)rcs1); + int **cs22 = combinationSum2(c2, ARRAY_SIZE(c2), 5, &rs2, (int **)rcs2); + for (int i = 0; i < rs2; i++) + for (int j = 0; j < rcs2[i]; j++) + printf("%d ", cs22[i][j]); + printf("\n"); + free(cs21), free(cs22), free(rcs1), free(rcs2); +} diff --git a/combination_sum2.py b/combination_sum2.py new file mode 100644 index 0000000..d1bbc5e --- /dev/null +++ b/combination_sum2.py @@ -0,0 +1,37 @@ +# 40. Combination Sum II + +""" +given a collection of candidate numbers and a target number, find all unique +combinations in 'candidates' where the candidate numbers sum to 'target'. +each number in 'candidates' may only be used once +""" + + +class Solution(object): + def dfs(self, candidates, target, idx, path, res): + if target <= 0: + if target == 0: + res.append(path) + return + for i in range(idx, len(candidates)): + if i > idx and candidates[i] == candidates[i - 1]: + continue + self.dfs( + candidates, target - candidates[i], i + 1, path + [candidates[i]], res + ) + + def combinationSum2(self, candidates, target): + """ + :type candidates: List[int] + :type target: int + :rtype: List[List[int]] + """ + ans = [] + self.dfs(sorted(candidates), target, 0, [], ans) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.combinationSum2(candidates=[10, 1, 2, 7, 6, 1, 5], target=8)) + print(obj.combinationSum2(candidates=[2, 5, 2, 1, 2], target=5)) |