[LeetCode] Combinations

https://leetcode.com/problems/combinations/

 

문제 파악

주어진 1~n까지의 범위 중에서, k개의 원소를 갖는 숫자 ‘조합’ 구하기

• 1 <= n <= 20
• 1 <= k <= n

접근 방법

💡 backtrack() 함수 정의하여, 가장 작은 단위의 연산을 정의하고, 재귀적으로 해당 함수를 호출한다.

 

코드 구현

class combinations {
    public List<List<Integer>> combine(int n, int k) {
        //1~n까지 숫자 중에 k개를 짝지은 조합을 찾아내기
        List<List<Integer>> result = new ArrayList<>();
        int start = 1; //시작점을 값으로 전달해주기. 
        // 함수에 유동적으로 인자를 주고 싶을 때 사용, 함수에 인자가 증가하며 삽입될 것이다.
        // 재귀 함수마다 다르게 하고 싶은 부분 = 시작점
        backtrack(start,n,k,result,new ArrayList<>());
        return result;
    }
    public void backtrack(int start,int n,int k,List<List<Integer>> result, List<Integer> comb){
        //base case
        if(comb.size()==k){
            result.add(new ArrayList<>(comb));
            return;
        }
        //recursive call
        for(int i=start;i<=n;i++){
            if(comb.contains(i)) continue;
            comb.add(i);
            backtrack(i+1,n,k,result,comb);//시작값 인자를 받아 증가된 값으로 재귀
            comb.remove(comb.size()-1);
        }
    }
}

배우게 된 점

• backtrack() 함수 인자값에 시작 인덱스 지정해주기

backtrack(start,n,k,result,new ArrayList<>());

-start 인자 = 함수에 유동적으로 인자를 주고 싶을 때 사용, 함수에 인자가 증가하며 삽입될 예정, 반복문 돌면서 i에 1더한 값 넣어주며 시작값 업데이트 -재귀 함수마다 다르게 하고 싶은 부분 = 시작점. 왜?

⇒ 매번 다른 시작점을 인자로 넘겨주어 순회 시 범위를 달리해야한다.

-1부터 n까지 순회 중, 한번 방문한 숫자는 재방문 없다는 것을 인지. 요소를 방문했으면 다음 요소부터는 제외하고 방문. 이미 다 조회했기 때문.

Q. comb.remove(comb.size()-1); 문제 없나? 리턴 후 무조건 제거 괜찮나?

⇒ backtrack함수의 리턴 조건은 1) comb.add 하거나 2) result.add(comb) 둘 중 하나이므로

comb의 값이 다르게 들어 갈 염려가 없다. 고로 remove를 수행할 시점이면 이미 result.add2) 된 상태. 원래는 반복 시작* 부분에서 재귀 함수가 계속 반복되었으나 if 구문으로 result.add되면 for문의 처음부터 다시 수행(comb.add) 그러면 remove 구문 또 문제없고.

⇒ 아무튼 결론은 재귀 함수 호출 이후 remove 저렇게 조건없이 호출해도 문제는 없다!