사칙연산을 활용해서 수들로 특정 수를 만들 수 있는지 확인하는 방법

안녕하세요. 팬메이드 게임을 만들던 도중 큰 장벽에 막히게 되어 글을 한 번 남겨보게 되었습니다.

본론부터 말하자면 숫자들과 사칙연산 그리고 괄호를 이용해 특정 수를 만들 수 있는지 확인할 수 있는 프로그램을 만들고 싶습니다.

예를 들자면 숫자 2, 3, 5, 7이 있을 때 사칙연산과 괄호를 통해 숫자들을 최대 한 번씩만 사용하며 27을 만들 수 있는지 판별할 수 있는 프로그램을 만들고 싶습니다. 위 예시대로 인풋이 들어올 시에 (2+7)*3 이런 식으로 리턴을 하게끔 말입니다.

프로그램을 만들어 달라 이런 류의 질문은 민폐니 단순한 접근법 혹은 알고리즘의 형태부터 알아가보고 싶습니다. 단순히 모든 가지수의 for loop로 돌리기엔 비효율적일 것 같고 재귀법을 사용하고자 하니 또 코드가 꼬이게 이게 맞나 싶네요. 이 문제를 어떤 식으로 접근하는 게 좋을까요?

재귀로 접근하는 게 맞다고 생각합니다.

제 생각에는 구한 값을 저장해서 사용하는 다이나믹프로그래밍(dp) 알고리즘을 사용하면, 시간을 상당히 절약할 수 있을 것 같아요.

피보나치 수열 같은 경우에는 dp를 직관적으로 쓸 수 있었는데 이 상황 같은 경우에는 단순치 않아서 괜히 막막해지네요. 숫자도 최대 한 번씩만 쓰일 수 있어서 배열들끼리 결합시키는 것도 꼬이지 않으려나요? 혹은 이중, 또는 그 이상의 차원 배열을 활용해서 다른 방향의 dp를 적용시키면 해결되려나요?

숫자를 한번씩만 사용할 수 있다면, 비트dp를 쓸 수도 있지 않을까요?
사칙연산이라 4가지의 경우가 있다면 시간복잡도를 비트dp처럼 줄이지 못하겠지만 비슷한 아이디어로 구현할 수도 있을 거 같아요.

정확한 조건을 모르는 제 입장에선 숫자가 많지만 않으면 그냥 재귀 완전탐색을 돌리고 싶네요.

정확한 조건을 명시하자면

숫자의 개수는 (1~10)의 숫자들 2 ~ 6개로 구성이 될 거에요.
사칙연산은 + / - / x / ÷ 이렇게 4가지 있으며 괄호도 사용 가능하게 할 생각입니다.
수를 만들 때 모든 숫자를 쓸 필요없어요. (2, 4, 6)이 있어도 2+4+6일 필요없이 2*6이어도 괜찮아요)

그 정도면 완전탐색을 돌려도 충분할 것 같습니다.

완전 탐색으로 한 번 해봐야겠네요. 도와주셔서 정말 감사합니당!