Combination Sum II[M,Array,Backtracking]

https://leetcode.com/problems/combination-sum-ii/?envType=daily-question&envId=2024-08-13

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

 

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

 

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

1. Python

시험에 나왔던 문제다.

개인적으로 너무 어렵다 진짜..

 

def combinationSum2(candidates,target):
    candidates.sort()
    results = []
    stack = [(0, 0, [])]  # (start_index, current_sum, current_path)
    while stack:
        start, curr_sum, path = stack.pop()
        if curr_sum == target:
            results.append(path)
            continue
        for i in range(start, len(candidates)):
            # 중복 제거
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            # 현재 선택한 수가 목표값을 초과하면 탐색 종료
            if curr_sum + candidates[i] > target:
                break
            # 다음 상태를 스택에 추가
            stack.append((i + 1, curr_sum + candidates[i], path + [candidates[i]]))
        print(stack)
        print(results)
    return results

# 테스트 코드
numbers =[10,1,2,7,6,1,5]
# [1,1,2,5,6,7,10]
target = 8
print(combinationSum2(numbers, target))

 

파이썬으로도 쩔쩔 매는데, 이거 C / C++로는 엄두가 나지도 않는다..

 

while문을 recursive하게 쓰면 아래와 같다.

 

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(start,target,path):
            if target == 0 :
                ans.append(path)
                return
            if target < 0 :
                return
            for i in range(start,len(candidates)):
                #for duplicate
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                backtrack(i+1,target-candidates[i],path+[candidates[i]])
        candidates.sort()
        ans = []
        backtrack(0,target,[])
        return ans

 

2. C

# C
#include <stdio.h>
#include <stdlib.h>

void backtrack(int* candidates, int candidatesSize, int target, int* path, int pathSize, int start, int** ans, int* ansSize, int** colSizes) {
    if (target == 0) {
        ans[*ansSize] = (int*)malloc(sizeof(int) * pathSize);
        for (int i = 0; i < pathSize; i++) {
            ans[*ansSize][i] = path[i];
        }
        (*colSizes)[*ansSize] = pathSize;
        (*ansSize)++;
        return;
    }
    
    for (int i = start; i < candidatesSize; i++) {
        if (i > start && candidates[i] == candidates[i - 1]) continue;
        if (target - candidates[i] < 0) break;
        
        path[pathSize] = candidates[i];
        backtrack(candidates, candidatesSize, target - candidates[i], path, pathSize + 1, i + 1, ans, ansSize, colSizes);
    }
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    qsort(candidates, candidatesSize, sizeof(int), compare);
    int** ans = (int**)malloc(1000 * sizeof(int*));
    int* path = (int*)malloc(candidatesSize * sizeof(int));
    *returnColumnSizes = (int*)malloc(1000 * sizeof(int));
    *returnSize = 0;
    
    backtrack(candidates, candidatesSize, target, path, 0, 0, ans, returnSize, returnColumnSizes);
    
    free(path);
    return ans;
}

int main() {
    int candidates[] = {10, 1, 2, 7, 6, 1, 5};
    int candidatesSize = sizeof(candidates) / sizeof(candidates[0]);
    int target = 8;
    int returnSize;
    int* returnColumnSizes;
    
    int** result = combinationSum2(candidates, candidatesSize, target, &returnSize, &returnColumnSizes);
    
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d%s", result[i][j], j == returnColumnSizes[i] - 1 ? "" : ", ");
        }
        printf("]\n");
        free(result[i]);
    }
    
    free(result);
    free(returnColumnSizes);
    
    return 0;
}

 

 

3. C++

# C++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void backtrack(vector<int>& candidates, int target, vector<int>& path, int start, vector<vector<int>>& ans) {
    if (target == 0) {
        ans.push_back(path);
        return;
    }
    
    for (int i = start; i < candidates.size(); i++) {
        if (i > start && candidates[i] == candidates[i - 1]) continue;
        if (target - candidates[i] < 0) break;
        
        path.push_back(candidates[i]);
        backtrack(candidates, target - candidates[i], path, i + 1, ans);
        path.pop_back();
    }
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> ans;
    vector<int> path;
    backtrack(candidates, target, path, 0, ans);
    return ans;
}

int main() {
    vector<int> candidates = {10, 1, 2, 7, 6, 1, 5};
    int target = 8;
    vector<vector<int>> result = combinationSum2(candidates, target);
    
    for (const auto& comb : result) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i] << (i == comb.size() - 1 ? "" : ", ");
        }
        cout << "]\n";
    }
    
    return 0;
}

 

쉽지 않다..