[LeetCode] 216번 문제를 풀어보았다. (ft. java)

2022년 05월 10일 화요일 - 기침이 오늘도 안멈춰...

오늘 올려볼 문제는 216번 Combination Sum III 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

요즘 회사에서 문제 풀 시간이 없네..

입력

사진에서도 볼 수 있듯이 int 값 2개가 입력으로 들어온다.

---

풀이 및 코드

1 ~ 9 까지의 숫자를 1개씩만 사용해 k개 만큼 합해서 n이 나오는 경우의 수를 모두 구하고 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈다.

제약 조건이 매우 작기 때문에 백트래킹을 사용해서 브루트 포스로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    int n;
    public List<List<Integer>> combinationSum3(int k, int n) {
        this.n = n;

        solve(k, 1, 0, new Stack<Integer>());

        return result;
    }

    public void solve(int k, int num, int sum, Stack<Integer> s)
    {
        if(sum > n) return;

        if(sum == n)
        {
            if(k != 0) return;

            result.add(new ArrayList(s));
        }

        for(int i = num; i <= 9; i++)
        {
            s.push(i);
            solve(k - 1, i + 1, sum + i, s);
            s.pop();
        }
    }
}

---

제출 화면

오늘은 아마 제약조건이 좀만 더 컸다면 어렵지 않았을까 생각되는 문제였다.

내일 문제도 재밌는 문제가 나왔으면 좋겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.