aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-13 01:26:24 -0600
committerJack Sangdahl <[email protected]>2024-08-13 01:26:24 -0600
commitf2d3cef7086d326f38224db98dd95f0b1fef6ebc (patch)
treeeef74debe471188a8d1569d52ce076516511e4d7
parent484e384acfe8544836814d1a0e044c15caa36768 (diff)
downloadleetcode-f2d3cef7086d326f38224db98dd95f0b1fef6ebc.tar.gz
leetcode-f2d3cef7086d326f38224db98dd95f0b1fef6ebc.zip
40. combination sum 2
-rw-r--r--combination_sum2.c60
-rw-r--r--combination_sum2.py37
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))