SubsetSum

K개의 원소중에서 몇개의 원소를 선택해 부분집합을만들고 그 부분집합의 합 N을 구해보자.

1. 비트연산자를 이용한 부분집합의 합

배열버전

public class SubsetSum2 {
	public static void main(String[] args) {
		String[] arr = { "a", "b", "c"};

		for (int i = 0; i < (1<<arr.length); i++) {		//1,2,3,4,~7
			System.out.print(i+"{");
			for (int j = 0; j < arr.length; j++) {
				if((i&(1<<j)) != 0) {				//1 AND (001,010,100...)=>000,011,101,
					System.out.print(arr[j]+ " ");
				}
			}
			System.out.println("}");
		}
	}
}

• 결과화면
  

ArrayList버전

import java.util.ArrayList;

//부분집합의 합계가 10이 되도록 부분집합을 출력하기
//ArrayList사용
public class SubsetSum4 {
	public static void main(String[] args) {
		int[] arr = {1,2,3,4,5,6,7,8,9,10};
		int ans = 0;
		int N =13;
		for (int i = 0; i < (1<<arr.length); i++) {		
			int tmp = 0;
			ArrayList<Integer> sub = new ArrayList<>();
			
			String str = "";
			for (int j = 0; j < arr.length; j++) {
				if((i&(1<<j)) != 0) {				//1 AND (001,010,100...)=>000,011,101,
					tmp += arr[j];
					sub.add(arr[j]);
				}
			}
			if(tmp == N) {
				ans++;
				System.out.println(sub);
			}
		}
		System.out.println("합계가 "+N+"이되는 부분집합의 개수는"+ans+"개입니다.");
	}

}

• 결과화면
  

2. 사용한 원소를 체크하면서 (boolean배열 사용) 합이 N 이 될때 출력.

(순열 만들기 응용)

import java.util.ArrayList;

public class SubsetSum {
	static int [] arr = {1,2,3,4,5};
	static boolean [] used;
	static ArrayList<Integer> result;
	static int N;
	public static void main(String[] args) {
		result = new ArrayList<>();
		used = new boolean[arr.length];
		N = 7;
		perm(0,0);
	}
	static void perm(int cnt,int sum ) {
		// 조합을 만들어보다가 부분집합의 합이 N 이 되면 result 출력하고 끝내고
		if(sum == N ) {
			System.out.println(result);
			return;
		}
		// 부분집합의 합이 N이 되지 못하고 조합을 다 돌아보앗으면 리턴하자 
		if(cnt >=arr.length) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			if(!used[i]) {
				used[i]= true;
				sum+=arr[i];
				result.add(arr[i]);
				perm(cnt+1,sum);
				used[i]=false;
				sum-=arr[i];
				result.remove(result.size()-1);
			}
		}
	}
}

• 결과화면
  

=> 만약에 중복을 제거하고 싶다면..?!
변수 k를 추가해주고 조합을 돌릴때 for문에서 0부터 차례대로 보는게 아니라 나 다음거 부터 보면서 순열을 만들수 있도록 하면 된다

3. 중복없는 부분수열의 합

package day1019.proj;

import java.util.ArrayList;

public class SubsetSum {
	static int [] arr = {1,2,3,4,5};
	static boolean [] used;
	static ArrayList<Integer> result;
	static int N;
	public static void main(String[] args) {
		result = new ArrayList<>();
		used = new boolean[arr.length];
		N = 7;
		perm(0,0,0);
	}
	static void perm(int cnt,int sum,int k) {
		// 조합을 만들어보다가 부분집합의 합이 N 이 되면 result 출력하고 끝내고
		if(sum == N ) {
			System.out.println(result);
			return;
		}
		// 부분집합의 합이 N이 되지 못하고 조합을 다 돌아보앗으면 리턴하자 
		if(cnt >=arr.length) {
			return;
		}
		for (int i = k; i < arr.length; i++) {
			if(!used[i]) {
				used[i]= true;
				sum+=arr[i];
				result.add(arr[i]);
				perm(cnt+1,sum,i);			//현재 인덱스를 다음 첫 인덱스로 보내준다. 
				used[i]=false;
				sum-=arr[i];
				result.remove(result.size()-1);
			}
		}
	}

}

• 결과화면