부분수열의 합

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

이번문제는 백트레킹! 부분수열의 합 입니다.

n개의 원소중에서 m개를 뽑았을때 합이 S 이면 결과값을 늘려나가는 방법을 이용했습니다.

여기서 m개의 범위는 1 <= m <=n 으로 하였습니다.

기본적으로 nCm (1<=m<=n) 일때 결과값이 S인 것을 찾는다고 생각하면 좋을것 같습니다.

N과 M (4)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

지금까지 순열, 조합, 중복 순열을 알아봤습니다.

마지막으로 중복 조합에 대해서 공부해 보겠습니다.

중복 조합에서는 next 인자의 값을 증가시키지 않고 전달하여 for문에서 다시 i=next 부터 찾도록? 구현해보았습니다.

문제

8

92

backtracking의 첫 문제는 n-queen 문제로 정했습니다.

n x n 의 행렬에 대각선, 가로, 세로가 겹치지 않도록 모든 행에 말을 두어 그 경우의수를 출력하는 문제입니다.

풀이 순서는 다음과 같습니다.

1. 모든 행에 말 배치하기

2. 가로 세로 대각선이 겹치지 않는다면 말을 두기

3. 모든행의 말을 두었다면 결과값 업데이트

코드