엔지니어 게시판
LeetCode 솔루션 분류

[5/10] 216. Combination Sum III

컨텐츠 정보

본문

[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

관련자료

댓글 3

mingki님의 댓글

  • 익명
  • 작성일
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;
    }
};

나무토끼님의 댓글

  • 익명
  • 작성일
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

austin님의 댓글

  • 익명
  • 작성일
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;
    }
};
전체 396 / 8 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 148 명
  • 오늘 방문자 2,163 명
  • 어제 방문자 5,332 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,047 명
알림 0