백준 3040 백설 공주와 일곱 난쟁이

www.acmicpc.net/problem/3040

3040번: 백설 공주와 일곱 난쟁이

---

중복을 허용하지 않는 조합으로 합이 100인 7명을 구함.

---

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class 백설공주와일곱난쟁이 {
/*
 * 구할것: 합이 100이되는 7개의 수
 * 9개중 7개를뽑아 합이 100이되는경우 sb.append //답은 항상 유일하게주어지므로
 */
	static StringBuilder sb;
	static int peoples[];//아홉 난쟁이를 담을 배열
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input/백설공주와일곱난쟁이.txt"));
		Scanner sc = new Scanner(System.in);
		sb = new StringBuilder();
		peoples = new int[9];
		for (int i = 0; i < 9; i++) {//아홉난쟁이 입력
			peoples[i] = sc.nextInt();
		}
		combination(new int[7],0,0);//일곱난쟁이 담을 배열, 인덱스, 뽑은수
		System.out.println(sb);
	}
	private static void combination(int[] sel, int idx, int k) {
		if ( k == sel.length) {//일곱개를 다 뽑았을때
			int sum=0;//난쟁이의 합을 담을 임시변수
			for (int i = 0; i < sel.length; i++) {
				sum += sel[i];
			}
			if(sum==100) {//100인경우에만 sb에 append
				for (int i = 0; i < sel.length; i++) {
					sb.append(sel[i]).append('\n');
				}
				return;//100인경우 더 볼 필요가없으므로 return
			}
			return;		
		}
		for (int i =idx; i < 9; i++) {
			sel[k]=peoples[i];
			combination(sel, i+1, k+1);//중복을 허용하지 않는 조합
		}
		
	}

}