[Algorithm] 조합 Combination

Permutation과 다르게 Combination.
내가 보려고 쓰는 글.
기억이 나기 위해 쓰는 글.

☁️구름에서 문제 풀다가 Combination 오래간만에 봤고 그래서 적어둬야지.
문제 출처 : 문제

import java.util.*;
class Main {	
	static int limit;
	static int max = 0;
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		limit = sc.nextInt();
		sc.nextLine();
		int count = sc.nextInt();
		sc.nextLine();
		String[] data = new String[1];
		data = sc.nextLine().split(" ");
		
		int[] list = new int[count];
		for(int i=0; i<count; i++) list[i] = Integer.parseInt(data[i]);
        
        //--------요기까진 신경 안 써도 되는 부분------//
		
		boolean[] visited = new boolean[count];		
		
		for(int r=1; r<= count; r++){
			comb(list, visited, 0, r);
		}
			
		System.out.println(max);
	}
	
	public static void comb(int[] list, boolean[] visited, int depth, int r){
		if(r==0){
			print(list, visited);
			return;
		}
		if(depth==list.length){
			return;
		}else{
			visited[depth] = true;
			comb(list, visited, depth+1, r-1);
			
			visited[depth] = false;
			comb(list, visited, depth+1, r);
		}
	}
	
	public static void print(int[] list, boolean[] visited){
		int result = 0;
		for(int i=0; i<list.length; i++){
			if(visited[i]){
				result += list[i];				
			}
		}
		if(result <= limit){
			if(max <= result){
				max = result;
			}
		}
	}
}

🌫 Remember Point

나는 백트래킹하지 않고 재귀를 할것이기에 어떤 방식으로 할지가 중요하다.

comb(데이터 배열, 방문 여부 배열, depth, 몇개의 조합을 찾을지 그 수)

ex) comb(arr, visited, 0, r)

• arr배열에서 visited로 각 아이템별 방문 여부를 관리하고 0번 아이템부터 시작해서 r개의 조합을 찾습니다.
• n을 굳이 넣지 않은 이유는 arr.length로 구할 수 있기에!

n이 5라면
1~5개 모든 조합을 찾고 싶다면 반복문을 돌려서 r부분을 하나씩 올려주면 된다.
딱 3개의 조합만을 찾고 싶다? r에 3넣으면 된다.🍊

📌 방문처리와 동시에 재귀호출+미방문 처리도 하자.

visited[depth] = true;
comb(list, visited, depth+1, r-1);			
visited[depth] = false;
comb(list, visited, depth+1, r);

핵심일 수 있는 부분.
방문처리한 아이템을 조합으로 뽑기 위한 2줄과
그 아이템을 다시 빼고 다른 조합을 만들기 위해
다시 재귀 호출하는 2줄이다.