LeetCode 솔루션

[5/10] 216. Combination Sum III

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.09 22:08

7,991 조회
3 댓글
0 추천
0 비추천
목록 게시글 쓰기

[LeetCode 시즌 3] 2022년 5월 10일 문제입니다.

https://leetcode.com/problems/combination-sum-iii/

216. Combination Sum III

Medium

298876Add to ListShare

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used.
Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Constraints:

2 <= k <= 9
1 <= n <= 60

#LeetCode, #Google, #Array, #Backtracking

링크

https://leetcode.com/problems/combination-sum-iii/ 1925 회 연결

익명
작성일 2022.05.09 23:26

C++
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Combination Sum III.
Memory Usage: 6.4 MB, less than 83.34% of C++ online submissions for Combination Sum III.

class Solution {
private:
    vector<vector<int>> res;
    
    void combination(vector<int> &comb, int idx, int n, int sum, int prev) {
        if (idx == comb.size()) {
            if (sum == n) {
                res.push_back(comb);
            }
            return;
        }
        for (int i = prev + 1; i <= 9 && sum + i <= n; ++i) {
            comb[idx] = i;
            combination(comb, idx + 1, n, sum + i, i);
        }
    }
    
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> comb(k, 0);
        combination(comb, 0, n, 0, 0);
        return res;
    }
};

익명
작성일 2022.05.09 23:33

Runtime: 45 ms, faster than 48.29% of Python3 online submissions for Combination Sum III.
Memory Usage: 13.8 MB, less than 79.39% of Python3 online submissions for Combination Sum III.

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        visited = set()
        ans = []
        def backtracking(num, k, total, temp):
            if k == 0:
                if total == n:
                    t = temp.copy()
                    ans.append(t)
                else:
                    return
                
            for i in range(num, 10):
                if i in visited: 
                    continue
                visited.add(i)
                temp.append(i)
                backtracking(i, k - 1, total + i, temp)
                temp.pop()
                visited.remove(i)
        backtracking(1, k, 0, [])
        return ans

익명
작성일 2022.05.10 00:24

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Combination Sum III.
Memory Usage: 6.4 MB, less than 58.80% of C++ online submissions for Combination Sum III.

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ret;
        auto check = [&](auto& self, int n, int from, vector<int>& v) -> void{
            if (v.size() == k - 1 && n >= from && n < 10){
                    v.emplace_back(n);
                    ret.emplace_back(v);
                    v.pop_back();
            } else for(int i = from; i < 9; ++i){
                v.emplace_back(i);
                self(self, n-i, i+1, v);
                v.pop_back();
            }
        };
        vector<int> v;
        check(check, n, 1, v);
        return ret;
    }
};