DigitBuilder [Subset sum problem]

Author

jexis06

2000

Given n number of segments, calculate how many different numbers can be formed, if the segments are used to construct digits following the standard seven-segment display.

All segments must be used. The numbers can't have leading zeros.

Example

• For n = 3, the output should be
  DigitBuilder(n) = 1.
  The only number you can form is 7.
• For n = 4, the output should be
  DigitBuilder(n) = 2.
  It is possible to create numbers 4 and 11.

• [input] integer n

  The number of segments, 0 ≤ n ≤ 15.

• [output] integer

  The number of different numbers possible to construct.

https://codefights.com/challenge/ox6RH9ZKBKq39SGhJ

성냥개비, 디지털문자, 도형 등 겉포장을 바꿔가면서 자주 나오는 유형의 문제다.

이름하여 Subset sum problem.

여기서는 어떤 숫자 n과 그보다 작은 숫자들이 주어졌을 때 더해서 n이 되는 숫자의 조합들을 찾아내는 방법을 찾아야 할 것 같다.

참조

- http://baboc.tistory.com/270

-http://blog.naver.com/PostView.nhn?blogId=takku04&logNo=150017480080&redirect=Dlog&widgetTypeCall=true

- http://stackoverflow.com/questions/3302814/how-to-find-all-matching-numbers-that-sums-to-n-in-a-given-array