순열

• 중복 X 순서 O
• 중복순열에서 같은 값(중복)만 빼준것 (ex 1,1 3,3 5,5)

	static void permutation(int[] arr, int[] sel, int k, boolean[] v) {
		if(k==sel.length) {
			System.out.println(Arrays.toString(sel));
			return;
		}
		
		for(int i=0; i<arr.length; i++) {
			//아직 안뽑은 애면 들어간다!
			if(v[i]) continue;
			
			v[i]=true;
			sel[k]=arr[i];
			permutation(arr, sel, k+1, v);
			v[i]=false;
		}
	}
}

중복순열

• 중복 O, 순서X
• 앞에서 뽑은애 또 뽑아도 되고, 순서만 다른것도 다른것으로 친다.
  • 즉 제외할 게 없는 완전탐색!

	/**
	 * 
	 * @param arr
	 * @param sel	뽑은 배열
	 * @param k	뽑을 인덱스
	 */
	private static void purmutation(int[] arr, int[] sel, int k) {
		
		if(k==sel.length) {
			//다 골랐어요
			System.out.println(Arrays.toString(sel));
			return;
		}
		
		for(int i=0; i<arr.length; i++) {
			sel[k] = arr[i];
			purmutation(arr, sel, k+1);
		}

조합

중복 X 순서 X

방법1

	private static void combination(int[] arr, int[] sel, int idx, int k) {
		if(k==sel.length) {
			System.out.println(Arrays.toString(sel));
			return;
		}
		for(int i=idx; i<arr.length; i++) {
			sel[k]=arr[i];
			//중복조합은 i, 조합은 i+1
			//나보다 앞에 있는 애들은 이미 겹치고(순서X), 나는 중복되니까(중복X), 나 다음부터 시작한다
			combination(arr, sel, i+1, k+1);
		}
	}

방법2

• PowerSet 방식 사용
• 뽑냐 안뽑냐의 경우로만 나눔

	/**
	 * @param chus	원본배열
	 * @param idx	원본 인덱스
	 * @param k		뽑을 인덱스
	 * @param sel	뽑은 배열 (고른 배열)
	 */
	static void recursive(int idx, int k, int[] sel) {
		
		
		//총 7개의 출력이 나온다. 왜냐하면 2^3 - 1(다뽑는 경우. 2개까지만 뽑으니까!)
		
		if(k==sel.length) {
			//다 골랐어요
			System.out.println(Arrays.toString(sel));
			return;
		}
		
		if(idx==arr.length) {
			//더 고를게 없어요
			System.out.print(k);
			System.out.println("안뽑");
			return;
		}
		//뽑는 경우
		sel[k]=arr[idx];
		recursive(idx+1, k+1, sel);
	
		//안뽑는 경우
		recursive(idx+1, k, sel);
	}

중복조합

• 중복 O, 순서X

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {1,3,5};
		combination(arr,new int[2], 0,0);

	}

	private static void combination(int[] arr, int[] sel, int idx, int k) {
		if(k==sel.length) {
			System.out.println(Arrays.toString(sel));
			return;
		}
		for(int i=idx; i<arr.length; i++) {
			sel[k]=arr[i];
			//나보다 앞에 있는 애들은 이미 겹친다. 나부터 시작
			combination(arr, sel, i, k+1);
		}
	}

파워셋

• 모든 부분집합 구하기
• 조건문을 통해 따라 n개짜리 부분집합을 구할 수 있다

/**
	 * 
	 * @param idx	원본 인덱스	
	 * @param k		뽑을 인덱스
	 * @param sel
	 */
	static void powerSet(int idx, int k, boolean[] sel) {
		
		if(idx==arr.length) {
//			System.out.println(Arrays.toString(sel));
//			몇개짜리 부분집합인지 고를 수 있음
//			if(k==2) {
				for(int i=0; i<sel.length; i++) {
					if(sel[i]) System.out.print(arr[i]+" ");
				}
				System.out.println();
//			}
			return;
		}
		
		//뽑는 경우
		sel[idx]=true;
		powerSet(idx+1,k+1,sel);
		//안뽑는 경우
		sel[idx]=false;
		powerSet(idx+1, k, sel);
		
	}