[LeetCode] 77. Combinations (Java, 조합)

leetcode.com/problems/combinations/

Combinations - LeetCode

 

## 접근방법

---

이 문제는 흔히 나오는 조합 문제이다. 지금까지 코드를 작성할 때, 단순히 재귀함수로 코드를 작성하도록 구현했었다. 시간이 20ms가 나와서, 다른 코드들을 참고해봤다.

 

 

다른 코드들을 보니, 지금가진 개수와 남은 개수들을 모두 써도 원하는 조합의 길이를 만들지 못한다면 탐색할 필요가 없다는 사실을 이용했다. 이 사실을 이용하면, 1ms로 시간이 엄청 줄어든다.

 

 

조합에 대해서, 깊게 생각해보지 않았지만 앞으로는 위의 방식대로 코드를 작성해야 효율적이다는 것을 깨달을 수 있었다. 위에서 말한 내용은 for문안에 if문을 이해하면 될 것이다.

 

 

## 해설코드

---

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    int nMax;
    int cMax;
    
    void comb(int cur, List<Integer> list){
        if(list.size() == cMax){
            result.add(new ArrayList<>(list));
            return;    
        }
        
        for(int i = cur; i <= nMax; i++){
            if(list.size() + nMax - i + 1 < cMax)
                break;
            
            list.add(i);
            comb(i + 1, list);
            list.remove(list.size() - 1);
        }
    }
    
    public List<List<Integer>> combine(int n, int k) {
        nMax = n;
        cMax = k;
        
        comb(1, new ArrayList<>());
        
        return result;
    }
}