len_, sum_ = map(int, input(":").split(' '))
list_ = list(map(int, input(":").split(' ')))
result = [sorted(x) for x in [[list_[i] for i in range(len(list_)) if j & (1 << i)]
                              for j in range(1, 1 << len(list_))]
              if sum(x) == sum_]
print('\n'.join([','.join(map(str, x)) for x in result]))

Python 3.5.2에서 작성하였습니다.
bit연산으로 부분집합을 구해서 풀었습니다.

java로 작성해봤습니다 지적 환영합니다

import java.util.*;
import java.io.*;

public class doll {

    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new File("c:/oop/doll.txt"));
        int n = sc.nextInt();
        int mubiao = sc.nextInt();
        ArrayList<Integer> nums = new ArrayList<Integer>();
        boolean[] result = new boolean[n];
        Random ran = new Random();
        while (sc.hasNext()){
            nums.add(sc.nextInt());
        }
        Collections.sort(nums);
        int sum=0;
        while(sum!=mubiao){
            sum=0;
            for(int i=0; i<n;i++){
                result[i]=ran.nextBoolean();
                if (result[i]==true) sum+=nums.get(i);
            }
        }
        for(int i=0; i<n;i++){
            if (result[i]==true) System.out.print(nums.get(i)+" ");


        }

    }

}

입력 값(doll.txt) 10 50

25 27 3 12 6 15 9 30 21 19

실행결과 6 19 25

while __name__ == '__main__':
    res = []
    for s in ['a, b', 'c']:
        exec(s + ''' = [*map(int, input('>>>').split())]''')
    _ = [*([*(res.append(j) for j in __import__('itertools').combinations(c, i+1) if sum(j) == b)] for i in range(a))]
    for i in res:
        print(i)

속도는 고려하지 않았습니다. 10개 수준에서는 즉시 나옵니다. 파이썬 3.5.2 64

입력을 다 처리했다 치면 main()은 아래처럼 만들어볼 수 있다.

int main(int argc, const char * argv[]) {
    int ns[] = {25,27,3,12,6,15,9,30,21,19};
    nsum(ns, 10, 50);
    return 0;
}

nsum()은 숫자들로 합계를 만들어보고 가능하면 그 값들을 출력해준다.

마치 여러가지 동전들로 특정 금액 만드는 문제와 비슷하다. 처음부터 하나씩 넣어보고(dfs) sum을 만들어보자.

void nsum(int ns[], int len, int sum) {
    int* answer = (int*)malloc(sizeof(int) * len);

    int* answer2 = dfs(ns, len, 0, answer, sum); // 0번부터 시작!
    if (answer2) {
        for (int* i=answer; i < answer2; i++) {  // 답을 찾았으면 숫자들 출력
            printf("%d ", *i);
        }
        printf("\n");
    } else {
        printf("impossible\n");
    }

    printf("%d steps\n", step); // 184
    free(answer);
}

dfs는 i번째 위치의 숫자를 넣는 경우와 넣지 않는 경우로 모든 경우를 검사한다. 그전에 재귀의 끝을 확인한다.

int* dfs(int ns[], int len, int i,
         int* answer, int sum) {
    if (sum == 0) // 답을 찾았다!
        return answer;
    if (i == len) // 더이상 처리할 숫자가 없다.
        return 0;

    // i를 넣거나
    *answer = ns[i];
    int *answer2 = dfs(ns, len, i+1, answer+1, sum-ns[i]);
    if (answer2) return answer2;

    // 넣지 않거나
    return dfs(ns, len, i+1, answer, sum);
}

그런데, 이러면 모든 경우를 살펴보는 것이고.. 미리 숫자가 정렬되어 있으면 앞으로 만들어야하는 합보다 남은 숫자들이 더 큰 경우 더 이상 테스트해볼 필요가 없다. (예, 10을 만들어야 하는데 11, 12, 13..이 남았다면 11뿐만 아니라 12, 13도 살펴볼 필요가 없다)

미리 정렬 해 놓고,

int intComp(const void* a, const void* b) {
    return *(int*)a == *(int*)b ? 0 : *(int*)a > *(int*)b ? 1 : -1;
}

void nsum(int ns[], int len, int sum) {
    qsort(ns, len, sizeof(int), intComp);
    ...
}

dfs()에서 만들 sum이 현재 값 ns[i]보다 작으면 i 뒤로는 볼 필요없다.

int* dfs(int ns[], int len, int i,
         int* answer, int sum) {
    if (sum == 0) // 답을 찾았다!
        return answer;
    if (i == len) // 더이상 처리할 숫자가 없다.
        return 0;
    if (ns[i] > sum) // i 뒤로는 볼 필요 없다.
        return 0;

    ...
}

Java

• 이진수를 이용해 모든 경우의 합을 계산하고 일치할 때 출력.
• break 문을 넣으면 처음 일치하는 경우만 출력.

import java.util.Scanner;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.regex.Pattern;

public class TargetDolls {
    public static void process(String input1, String input2) {
        String[] inputList1 = Pattern.compile(" ").split(input1);
        int size = Integer.parseInt(inputList1[0]);
        int targetSum = Integer.parseInt(inputList1[1]);
        int[] sortedList = Pattern.compile(" ").splitAsStream(input2)
                .mapToInt(Integer::parseInt).sorted().toArray();
        int binaryMax = (int)Math.pow(2d, (double)size);
        for (int i = 1; i < binaryMax; i++) {
            if (computeSum.apply(i, sortedList) == targetSum) {
                showResult.accept(i, sortedList);
                //break;
            }
        }
    }

    private static BiFunction<Integer, int[], Integer> computeSum = (caseNum, values) -> {
        int pos = 0, sum = 0;
        while (caseNum > 0) {
            sum += caseNum % 2 == 1 ? values[pos]:0;
            pos++;
            caseNum = caseNum/2;
        }
        return sum;
    };

    private static BiConsumer<Integer, int[]> showResult = (caseNum, values) -> {
        int pos = 0;
        while (caseNum > 0) {
            System.out.print(caseNum % 2 == 1 ? values[pos]+" ":"");
            pos++;
            caseNum = caseNum/2;
        }
        System.out.println();
    };

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            String input1 = sc.nextLine();
            String input2 = sc.nextLine();
            TargetDolls.process(input1, input2);
        }
    }
}

결과

• 입력: 5 10
• 입력: 1 2 3 4 5
• 1 2 3 4
• 2 3 5
• 1 4 5

Ruby

두가지로 풀었습니다. 첫째, combination. 둘째, 인형의 수가 아주 많아질 경우를 상정한 conditional combination구현.

def lottery_game
  (n, sum), nums = 2.times.map { gets.split.map(&:to_i) }
  (1..n).flat_map {|i| nums.combination(i).select {|e| e.sum(0) == sum } }
        .map {|e| puts e.sort.join(' ') }
end

Test

$stdin = StringIO.new("10 50\n25 27 3 12 6 15 9 30 21 19\n")
expect { lottery_game }.to output("6 19 25\n").to_stdout

Output

lottery_game
10 50
25 27 3 12 6 15 9 30 21 19

Ruby - Conditional combination

combination 생성범위를 줄이기 위해서 두가지 조건을 줍니다. combination(depth+1)은 head, rest[1,1]로 생성하는데 둘의 합이 50보다 클 때만 생성합니다. combination(depth)는 head, rest[0]과 rest[1..-1]중 한개의 수로 생성하는데, 앞의 head와 rest[0]합이 sum보다 작거나 같을 때만 동작합니다. 범위가 극단적으로 줄어드므로 훨씬 빠릅니다. 재귀로 구현했는데 깔끔치는 않네요.

def lottery_game_fast
  (n, sum), nums = 2.times.map { gets.split.map(&:to_i) }
  comb = ->head,rest,out do
    return out if (head + rest).empty?
    if rest.empty?
      head.sum == sum ? out << head : out
    else
      comb[head +[rest[0]], rest[1..-1], out] if head.sum(0) <= sum - rest[0]
      (head + rest[1..-1]).sum(0) >= sum ? comb[head, rest[1..-1], out] : out
    end
  end

  puts comb[[],nums,[]].map {|e| e.sort.join(' ') }
end

Performance

$stdin = StringIO.new("10 50\n25 27 3 12 6 15 9 30 21 19\n")
puts Benchmark.realtime { lottery_game } 
6 19 25
0.0011008729925379157

$stdin = StringIO.new("10 50\n25 27 3 12 6 15 9 30 21 19\n")
puts Benchmark.realtime { lottery_game_fast }
6 19 25
0.000771850987803191

(수정)

디디님 너무 좌절하시는 거 같아서....

N개의 숫자에 대해서 임의의 A개의 숫자를 골라 더할 수 있는 경우는 2^N이고, 전체 케이스를 완전 탐색한다고 하면, 지수적 시간복잡도를 갖는 문제이고, 다항 시간 내에 풀기도 쉽지 않을 것 같습니다. 만약 문제에서 "전체 조합을 구하라" 같은 조건이 명시돼 있었다고 가정하면...

만약 입력된 숫자들이 오름차순으로 정렬되어 있다고 할 때 작은 숫자부터 우선 선택하며, 선택한 숫자의 개수도 작도록 숫자를 선별합니다. K 개의 숫자를 골라서 고른 숫자의 합이 S보다 작으면 버리고, 일치하면 줍습니다. 그리고 S보다 크면 K개 조합의 그 이후 버전은 다 볼필요가 없으므로 건너뛸만하겠죠.

이런식으로 볼 필요가 없는 부분들을 빼고 검사해나가면 좀 더 빠르게 풀 수 있습니다만, 숫자의 개수가 아주 많고, 1, 2, 3 등 작은 값들의 비율이 크고 S가 꽤 큰 값이라면 이것 역시 시간이 오래 걸릴 수 밖에 없습니다.

from itertools import combinations

def do2(n, xs):
    result = []
    xs.sort()
    for i in range(2, len(xs)+1):
        cb = combinations(xs, i)
        for ys in cb:
            if sum(ys) == n:
                result.append((*ys,))
            elif sum(ys) > n:
                break
    return [sorted(x) for x in result]

def main2():
    n, s = [int(x) for x in input().split()][:2]
    xs = [int(x) for x in input().split()][:n]
    result = do2(s, xs)
    print("\n".join(str(x) for x in result))
    print('done')

# >>> 344 1888
# >>> 2 9 11 12 14 17 20 22 25 26 28 33 36 44 50 52 59 61 66 79 80 88 91 93 94 96 102 103 104 109 113 118 120 128 132 134 136 137 145 147 148 149 154 157 158 162 163 166 168 169 172 173 174 176 178 179 180 181 184 193 195 196 199 201 202 210 213 216 217 218 221 232 235 236 237 244 248 250 251 252 253 257 260 264 268 277 278 287 289 291 293 299 301 302 303 304 305 306 308 317 319 322 325 328 329 330 332 333 338 342 345 349 351 355 356 357 358 359 360 364 366 369 370 371 372 375 383 384 386 390 396 399 400 402 403 404 409 412 413 415 417 419 424 425 426 443 444 447 448 449 454 457 463 465 469 471 478 479 480 482 486 487 490 492 497 498 499 502 504 506 512 513 518 520 521 522 525 526 533 537 538 540 543 547 551 553 555 556 558 559 562 566 567 572 574 575 577 580 581 582 583 585 590 594 598 599 600 603 604 610 612 615 625 628 633 635 639 643 644 651 652 654 655 658 660 664 665 667 669 673 676 678 680 684 685 687 688 689 690 691 695 696 700 702 706 712 718 719 721 722 724 726 727 732 734 735 739 740 745 746 750 751 752 753 754 755 757 759 761 765 766 767 771 773 777 782 783 785 790 794 795 799 812 815 819 821 823 826 827 830 833 838 845 846 847 848 850 851 856 857 858 862 867 868 876 878 880 883 890 892 900 908 910 914 917 918 919 921 922 923 924 930 932 937 940 946 947 949 952 954 959 961 969 971 973 977 978 979 982 986 988 990 994 999

[2, 9, 878, 999]
[2, 9, 11, 867, 999]
[2, 9, 11, 12, 14, 17, 20, 22, 782, 999]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 757, 999]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 590, 999]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 50, 540, 999]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 50, 52, 59, 61, 66, 302, 999]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 50, 52, 59, 61, 66, 79, 232, 990]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 50, 52, 59, 61, 66, 79, 80, 88, 91, 93, 94, 96, 680]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 50, 52, 59, 61, 66, 79, 80, 88, 91, 93, 94, 96, 102, 103, 104, 371]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 50, 52, 59, 61, 66, 79, 80, 88, 91, 93, 94, 96, 102, 103, 104, 109, 113, 149]

done 
( 959 ms )

역시나 속도는 할말 없습니다;;; python3.5입니다.

def do(s, xs):
    if s == 0:
        return [], True
    for i, x in enumerate(xs):
        ys = xs[:i] + xs[i+1:]
        zs, r = do(s-x, ys)
        if r:
            zs.append(x)
            return zs, True
    return [], False


def main():
    n, s = [int(x) for x in input().split()][:2]
    xs = [int(x) for x in input().split()][:n]
    result, r = do(s, xs)
    if r:
        print(' '.join(str(x) for x in sorted(result)))
    else:
        print('no combination')


if __name__ == '__main__':
    main()

파이썬3.5

죄송합니다... 위 댓글에는 지적질을 했는데 정작 제풀이는 형편이 없습니다.
속도도 최악입니다. 어떻게 손을 써볼수가 없었습니다.
입력, 출력 풀어조건에도 맞질 않습니다. 속도가 느리니 즐겁지가 않아 여기까지만 했습니다.

def f(a, target):

    a = sorted(a)
    result = set()

    def g(a):

        if sum(a) == target:
            result.add(tuple(a))
            return

        elif sum(a) < target:
            return

        else:
            for i in range(len(a)):
                x = a[:i] + a[i+1:]
                g(x)

    g(a)

    return result


a = [25, 27, 3, 12, 6, 15, 9, 30, 21, 19]
target = 50
f(a, target)

파이썬3.4.3

위의 방식보다 획기적으로 속도개선을 했습니다. 그러나 느리지요. 왜냐하면 완전탐색이니까요ㅜㅜ
보다 나은 알고리즘을 공부하면 다시 올리겠습니다.

# 제출 코드

# 입력
n, goal = tuple(map(int, input().split()))
a = sorted(list(map(int, input().split())))
assert len(a) == n

# 처리
result = []
def shot(last=0, picked=None, score=0):

    global result

    if picked is None:
        picked = []

    # 기저사례
    if score == goal:
        return picked

    elif score > goal:
        return False

    for i in range(last, n):      
        picked.append(a[i])
        ret = shot(i+1, picked, score+a[i])
        if ret: result.append(ret[:])    # result.append(ret)는 빈값이 됨.
        picked.pop()

# 출력
shot()
for line in result:
    for case in line:
        print(case, end=' ')
    print()

using System;
using System.Collections;
using System.Collections.Generic;

namespace CodingTest
{
    class Program
    {
        private static int sum = 50;
        private static int[] entities = new int[] { 25, 27, 3, 12, 6, 15, 9, 30, 21, 19 };
        private static List<string> itemSet = new List<string>();

        static void Main(string[] args)
        {
            Array.Reverse(entities);
            for (int i = 0; i < entities.Length; i++)
            {
                checkToSum(i);
            }
            foreach (string im in itemSet)
            {
                Console.WriteLine(im);
            }
            Console.ReadLine();
        }

        static void checkToSum(int startIdx)
        {
            int targetInt = sum - entities[startIdx];
            int parentInt = 0;
            int childInt = 0;
            for (int i = 0; i < entities.Length; i++)
            {
                if (entities[i] == entities[startIdx] || parentInt == entities[startIdx]) continue;
                if (parentInt == 0) parentInt = entities[i];
                childInt = entities[i];
                if (parentInt == childInt) continue;
                if (targetInt == parentInt + childInt)
                {
                    ArrayList ax = new ArrayList();
                    ax.Add(entities[startIdx]);
                    ax.Add(parentInt);
                    ax.Add(childInt);
                    ax.Sort();
                    string result = string.Format("{0} {1} {2}", ax[0], ax[1], ax[2]);
                    if (itemSet.FindAll(x => x == result).Count == 0)
                        itemSet.Add(result);
                    return;
                }
            }
        }
    }
}

import java.util.Random;* 

public class DollHitter {

    public static void main(String args[]){

    int num = 15;
    int sum = 60;
    Random ran = new Random();

    int arr[] = new int[num];
    for(int i = 0 ; i < num ; i++){

        arr[i] = ran.nextInt(30)+1;
        for(int j = 0 ; j < i ; j++){
            if(arr[i] == arr[j]){
                i--;
            }
        }
    }
    중복되지 않는 30 이하 난수 15개 생성 (제한 포인트는 맘대로 지정하셔도 됩니다)

    for(int i = 0 ; i < arr.length ; i++){
        System.out.print(arr[i]+" : ");
    }

    int set[] = {};

    for(int i = 0 ; i < arr.length ; i++){
        set = new int[3];
        set[0] = arr[i];
        for(int j = i+1 ; j < arr.length ; j++){
            set[1] = arr[j];
            for(int k = j+1 ; k < arr.length ; k++){
                set[2] = arr[k];
                if(set[0]+set[1]+set[2] == sum){
                    System.out.println(set[0]+" : "+set[1]+" : "+set[2]);
                }

            }
        }

    }

    바깥 for문은 생성된 난수 배열의 합이 60이 되는 세개의 숫자중 첫번재 숫자
    중간 for문은 생성된 난수 배열의 합이 60이 되는 세개의 숫자중 두번재 숫자
    안쪽 for문은 생성된 난수 배열의 합이 60이 되는 세개의 숫자중 세번째 숫자




    }

}

subsquence를 뽑아낼 때 재귀를 사용했습니다. 파이썬 3을 사용하였습니다.

def combination(x):
    if len(x)==1:
        return [[x[0]]]
    else:
        smallercombi=combination(x[:len(x)-1])
        realcombi=smallercombi[:]
        for smaller in smallercombi:
            realcombi.append(smaller+[x[len(x)-1]])
        realcombi.append([x[len(x)-1]])
        return realcombi

numofdoll, target =  map(int, input("두 수를 공백으로 구분하여 입력하시오 : ").split())
numlist = []
for x in range(numofdoll):
    numlist.append(int(input("인형에 써진 수를 입력하시오 : ")))
subsequence = combination(numlist)
for sub in subsequence:
    if sum(sub) == target:
        sub.sort()
        print(sub)

def sublist_(a):
    sublist=list()
    result=[]
    for i in range(1,1<<len(a)):
        k=str(bin(i))
        r=0
        for j in reversed(k[2:]):
            if j=="1":
               sublist.append(a[r])
            r+=1
        result.append(sublist)
        sublist=[]
    return result
a,b=map(int,input().split(" "))
setlist=list(map(int,input().split(" ")))
setlist_=sublist_(setlist)
for i in setlist_:
    if sum(i)==a:
        print(i,end=" ")

전체 부분 집합을 만들고 합을 구해서 같으면 출력합니다.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class AmusementPark {

    public static void main(String[] args) throws FileNotFoundException {
        String path = AmusementPark.class.getResource("").getPath();
        Scanner sc = new Scanner(new File(path + "AmusementPark.txt"));

        int size = sc.nextInt();
        int target = sc.nextInt();
        int[] dolls = new int[size];

        for (int i = 0; i < size; i++) {
            dolls[i] = sc.nextInt();
        }

        for (int i = 1; i < 1 << size; i++) {
            int k = i;
            int d = 0;
            List<Integer> t = new ArrayList<>();
            while (k > 0) {
                if (k % 2 == 1) t.add(dolls[d]);
                k = k / 2;
                d++;
            }
            if (t.stream().mapToInt(Integer::intValue).sum() == target) {
                System.out.println(t);
            }
        }
    }
}

def doll(data):
    n,limit=data[0]
    data=sorted(data[1])
    if sum(data)<limit or min(data)>limit:
        return -1
    for i in range(n):
        if data[i]==limit:
            return [data[i]]
        elif doll([[n-1,limit-data[i]],data[0:i]+data[i+1:]])==-1:
            pass
        else:
            return [data[i]]+doll([[n-1,limit-data[i]],data[0:i]+data[i+1:]])
    return -1
doll([[10,50],[25, 27, 3, 12, 6, 15, 9, 30, 21, 19]])

우선은 brute-force 방법으로 MATLAB 짜보았습니다

clear all
close all
clc

t_start=clock;

% brute-force combination


%% input values

input_val1=str2num(input('인형갯수 필요한합 ','s'));
dolls_N=input_val1(1);
target_sum=input_val1(2);

dolls_input=str2num(input(sprintf('인형숫자들 (%d개) ',dolls_N),'s'));


%% find the combinations 
dolls_sorted=sort(dolls_input,'ascend');

% length would be 2^N, where N is the number of the dolls
solution_cnt=0;
solution_arr_aloc=cell(2^dolls_N,dolls_N);

% find all combination
% example, if there are 3 numbers, the combination would be 2^3 - 1 = 7
% X X O
% X O X 
% O X X
% X O O
% O X O
% O O X
% O O O

for n=1:2^dolls_N-1

    % at this combination, collect the index numbers
    test_array=[];
    tmp=n;
    for p=dolls_N:-1:0
        if tmp >= 2^p
            test_array=[test_array p+1];
            tmp=tmp-2^p;
        end
    end

    % if the sum of the selected dolls is equal to the target num, save it
    if sum(dolls_input(test_array))==target_sum
        solution_cnt=solution_cnt+1;
        solution_arr_aloc{solution_cnt}=dolls_input(test_array);
    end
end

refined_solution_arr_aloc=cell(solution_cnt,dolls_N);
for q=1:solution_cnt
    refined_solution_arr_aloc{q}=solution_arr_aloc{q};
end
clear solution_arr_aloc

%% show the result
disp(['number of combinations : ' num2str(solution_cnt)]);
for q=1:solution_cnt
    sort(refined_solution_arr_aloc{q},'ascend')
end


%% show the elapsed time
t_finish=clock;
elapsed_time=etime(t_finish,t_start);

if elapsed_time<60
    disp(['    elapsed time : ' num2str(elapsed_time) ' sec']);
elseif elapsed_time<3600
    disp(['    elapsed time : ' num2str(elapsed_time/60) ' mins']);
else    
    disp(['    elapsed time : ' num2str(elapsed_time/3600) ' hours']);
end

package codingdojang;

import java.util.Scanner;

public class doll {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner s=new Scanner(System.in);

    int dollCnt=s.nextInt();
    int dollSum=s.nextInt();
    int arr[]=new int[dollCnt];
    for(int i=0;i<dollCnt;i++){
        arr[i]=s.nextInt();
    }
    int n1=0,n2=0,n3=0;
    for(int i=0;i<10;i++){
        for(int j=i+1;j<10;j++){
            for(int k=j+1;k<10;k++){
                if(arr[i]+arr[j]+arr[k]==50){
                    n1=i;
                    n2=j;
                    n3=k;
                    break;
                }
            }
        }
    }
    System.out.println(arr[n1]+" , "+arr[n2]+" , "+arr[n3]);
}

}

print('dsd')

javascript

주어진 수열을 가지고 만들 수 있는 모든 조합을 생성한 후,

합이 50이 되는 것을 필터링하고

소트해서 보여줍니다.

var input = 
`10 50
25 27 3 12 6 15 9 30 21 19`;

var [[count, sum], dolls] = input.split("\n").map($ => $.split(" ").map($ => parseInt($)));

var combination = function combination(array){
    if (array.length === 0)
        return [[]];
    var combs = [];
    for (var i = 0; i <= array.length; i++){
        var head = array.slice(i, i + 1),
            tail = array.slice(i + 1),
            tailcombs = combination(tail);
        combs.push(...tailcombs.map($ => head.concat($)))
    }
    return combs;
};

var result = combination(dolls).filter($ => $.reduce((a, b) => a + b, 0) === sum)
                               .map($ => $.sort((a, b) => a - b));

console.log(result.map($ => $.join(" ")).join("\n"));

array = input("input number array : ")
tgt = input("input target sum : ")


array = [int(x) for x in array.split(" ")]
result = []
result_list = []

for i in range(0,len(array)):
    for j in range(i+1,len(array)):
        for k in range(j+1,len(array)):
            if (array[i] + array[j] + array[k]) == int(tgt):
                result = sorted([array[i], array[j], array[k]])
                result_list.append(result)


for l in range(0,len(result_list)):
    for m in range(l+1,len(result_list)):
        if result_list[l] == result_list[m]:
            del(result_list[m])
            break


print (result_list)

shoot()은 맞춘 인형 중 가장 숫자가 큰 인형을 뽑는 함수입니다.

예를 들어 인형이 1 2 3 4 5 가 있다고 할 떄,

숫자가 큰 인형부터 맞춘다고 가정하면(결과가 숫자의 조합이기 때문에 무리 없는 가정)

첫 번쨰로 5를 맞춘 경우, 첫 번째로 4를 맞춘 경우, ... 1을 맞춘 경우가 생깁니다.

요점은 지금 맞춘 인형이 "가장 숫자가 큰" 인형이기 때문에 그보다 숫자가 큰 인형을 제외할 수 있습니다.

즉 첫 번째로 5를 맞췄으면 두 번째 숫자가 큰 인형은 1 2 3 4 중 하나,

첫 번째로 4를 맞췄으면 다음에는 1 2 3 중 하나,

첫 번쨰로 3을 맞췄으면 다음에는 1 2 중 하나,

첫 번째로 2를 맞췄으면 다음에는 1 이 됩니다.

물론 합이 다 찼으면 다음으로 넘어가지 않고 중단합니다.

def shoot(dolls, sum, hits):
    if sum == 0: return hits
    if sum < 0: return None

    while dolls:
        hit = dolls.pop()
        ret = shoot(dolls[:], sum - hit, [hit] + hits)
        if ret: return ret
    return None

inp = '''10 50
25 27 3 12 6 15 9 30 21 19'''

inp = list(map(int, inp.split()))
print(shoot(sorted(inp[2:]), inp[1], [])) # 6 19 25

만약 인형 개수가 정해져 있어서 위의 재귀함수를 for문으로 처리한다면 이런 형태가 됩니다.

for i in range(len(dools)):
    for j in range(i+1, len(dools)):
        for k in range(j+1, len(dools)):
            ...
                if dools[i] + dools[j] + dools[k] + .... == sum:
                    return [..., dools[k], dools[j], dools[i]]

# 맞춘 인형은, 서있는 목록에서 넘어진 목록으로 넘긴 후,
# 점수가 같을 때까지 재귀로 찾기
def find(score, fallen_list, standing_list):
    if sum(fallen_list) == score:
        print("find! ", sorted(fallen_list))
    elif sum(fallen_list) < score:
        for i, x in enumerate(standing_list):
            find(score, fallen_list + [x], standing_list[(i + 1):])


fallen_list = []
standig_list = [25, 27, 3, 12, 6, 15, 9, 30, 21, 19]
score = 50
find(score, fallen_list, standig_list)

파이썬 3.6

"""
아이디어>
 1) 첫 번째 인형의 점수가 목표 점수와 같은지, 작은지, 큰지 확인 합니다.
 2) 첫 번째 인형의 점수가 목표 점수보다 작으면, 그 다음 순서 인형의 점수와 합하여 다시 목표 점수와 비교합니다.
 3) 첫 번째 두번째 인형의 점수가 목표 점수보다 작으면 나머지 인형들을 목표 점수와 같거나 초과 할때까지 누적 합산합니다.(목표 점수가 될 수 있는 인형의 수는 정해져 있지 않으므로 모든 인형 조합에 대해 목표점수를 비교합니다.)
 4) 모든 인형의 조합에 대해 위와 같은 과정을 반복하며, 목표 점수와 같은 경우 출력합니다. 
"""

def inputdata():
    n = input('').split()
    points = input('').split()
    data = [n,points]
    return data

def shotdoll(data):
    aim,point,t,tmp = int(data[0][1]),0,0,[]
    print("\n""목표 점수 = %d"%aim)
    for i,value_i in enumerate(data[1]):
        for h,value_h in enumerate(data[1][i+1:]):
            if int(value_i) == aim:
                tmp.append(int(value_i))
                print(' '.join(answer))
                break
            elif int(value_i) > aim:
                break
            if i+h < len(data[1])-1:
                point = int(value_i) + int(value_h)
                tmp = [int(value_i),int(value_h)]
                if point == aim:
                    answer = map(str,sorted(tmp))
                    print(' '.join(answer))
                    break
                while True:
                    t += 1
                    if i+h+t <= len(data[1])-1:
                        point += int(data[1][h+t])
                    else:
                        break
                    if point < aim:
                        tmp.append(int(data[1][h+t]))
                    elif point == aim:
                        tmp.append(int(data[1][h+t]))
                        answer = map(str,sorted(tmp))
                        print(' '.join(answer))
                        break
                    else:
                        tmp = [int(value_i),int(value_h)]
                        point = int(value_i)+int(value_h)
                tmp,t = [],0

if __name__ == "__main__":
    data = inputdata()
    shotdoll(data)

• 결과값

10 50
25 27 3 12 6 15 9 30 21 19

목표 점수 = 50
6 19 25

def dolls(m, b):
    b.sort()
    result = list()
    def doll(n, a):
        result = list()
        if sum(a) == n:
            return [a]
        elif sum(a) < n:
            return []
        for i in range(len(a)):
            for j in doll(n-a[i], a[i+1:]):
                result.append([a[i]]+j)
        return result
    for i in range(len(b)):
        result += doll(m, b[:i+1])
    return result

Input = [[10, 50], [25, 27, 3, 12, 6, 15, 9, 30, 21, 19]]

def fitScore(inpu):
    n = inpu[0][0]
    maxScore = inpu[0][1]
    score = inpu[1]
    outpu=inpu[2]
    if n==1:
        if maxScore != score[0]:
            return [0,[]]
        else:
            return [1,outpu+[socre[0]]]
    if sum(outpu)>maxScore:
        return [0,[]]
    for i in range(n):
        if maxScore==score[i]:
            return [1,outpu+[score[i]]]
        else:
            if fitScore([[n-1,maxScore-score[i]],score[0:i]+score[i+1:],outpu+[score[i]]])[0]==1:
                return fitScore([[n-1,maxScore-score[i]],score[0:i]+score[i+1:],outpu+[score[i]]])
    return [0,[]]
print(sorted(fitScore(Input+[[]])[1]))

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>    // malloc, free 함수가 선언된 헤더 파일

int compare(const void *a, const void *b)    // 오름차순 비교 함수 구현
{
    int num1 = *(int *)a;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴
    int num2 = *(int *)b;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴

    if (num1 < num2)    // a가 b보다 작을 때는
        return 1;      // -1 반환

    if (num1 > num2)    // a가 b보다 클 때는
        return -1;       // 1 반환

    return 0;    // a와 b가 같을 때는 0 반환
}



int fit_score(int inpu0,int inpu1,int  *inpu2) {
    int n = inpu0;
    int max_score = inpu1;

    if (n == 1) {
        if (inpu2[0] == max_score) {
            return max_score;
        }
        else {
            return 0;
        }
    }
    int* score = malloc(sizeof(int) *(n - 1));
    for (int i = 0; i < n; i++) {
        int k = 0;
        for (int j = 0; j < n; j++) {
            if (i != j) {
                score[k] = inpu2[j];
                k++;
            }
        }

        if (max_score > inpu2[i]) {
            int re = fit_score(n - 1, max_score - inpu2[i], score);

            if (re==0) {
            }
            else {
                printf("%d ", inpu2[i]);
                free(score);
                return re;
            }
        }
        else if (max_score==inpu2[i]){
            free(score);
            printf("%d ", inpu2[i]);
            return max_score;

        }



    }

    free(score);
    return 0;
}


int main() {
    int n = 10;
    int **input = malloc(sizeof(int*) * 2);
    input[0]= malloc(sizeof(int) * 2);
    input[1] = malloc(sizeof(int)*n);

    input[0][0] = n;
    input[0][1] = 50;

    input[1][0] = 25;
    input[1][1] = 27;
    input[1][2] = 3;
    input[1][3] = 12;
    input[1][4] = 6;
    input[1][5] = 15;
    input[1][6] = 9;
    input[1][7] = 30;
    input[1][8] = 21;
    input[1][9] = 19;

    qsort(input[1], n, sizeof(int), compare);

    fit_score(input[0][0], input[0][1], input[1]);


    free(input[0]);
    free(input[1]);
    free(input);
    return 0;
}

Swift입니다.

재귀호출로 풀었습니다. 재귀 함수는 만들고자 하는 합과 배열을 받습니다. 재귀 호출이 반복 되면, 조합을 발견하게 되는 경우, 마지막에는 주어진 총합과 같은 배열항목을 배열에서 찾게 됩니다.

주어진 점수들 중에서 2개 이상의 조합이 있는 경우, 첫번째 발견된 조합만을 리턴하게 되는 제한이 있네요.

import Foundation

func findSum(_ targetSum: Int, _ givenNumbers: [Int]) -> [Int] {
    var numbers = givenNumbers.sorted()
    var foundSeries = [Int]()
    var found = false
    for i in 0..<numbers.count {
        if numbers[i] < targetSum {
            let returnArray = findSum(targetSum - numbers[i], Array(numbers[(i + 1)..<numbers.count]))
            if returnArray.count > 0 {
                found = true
                foundSeries.append(numbers[i])
                foundSeries += returnArray
                break
            }
        } else if targetSum == numbers[i] {
            foundSeries.append(numbers[i])
            found = true
            break
        }
    }
    return found ? foundSeries : []
}

let targetScore = Int(readLine()!)!
let scoreInput = readLine()!.split(separator: " ")
let scores = scoreInput.map({return Int($0)!})

print( findSum(targetScore, scores) )

Doll <- function(x, target){
  library(dplyr)
  subset_list <- 1:8 %>% sapply(combn, x=x)  
  istarget <- lapply(subset_list, function(x) apply(x,2,sum)) %>% lapply(function(x) x==target) 
  target_list_number <- which((istarget %>% lapply(function(x) any(sum(x)==1)) %>% unlist) == T)
  return(subset_list[[target_list_number]][,which(istarget[[target_list_number]]==T)] %>% sort())
}

Doll(c(25,27,3,12,6,15,9,30,21,19), 50)
[1]  6 19 25

체이닝을 위해 dplyr패키지만 불러왔습니다. 1. 모든 조합 (부분집합)을 만들고 다 더합니다. 2. target과 같은지 검사 합니다.

재귀호출로 풀었습니다.

import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author Kimseongsu
 * @see http://codingdojang.com/scode/531
 * 
 */
public class Problem531 {

    static int SIZE;
    static int TARGET_SCORE;
    static Integer[] SCORES;

    public static void main(String[] args) {
        String[] INPUT = {
                "10 50",
                "25 27 3 12 6 15 9 30 21 19"
        };

        SIZE = Integer.valueOf(INPUT[0].split(" ")[0]);
        TARGET_SCORE = Integer.valueOf(INPUT[0].split(" ")[1]);
        SCORES = Stream.of(INPUT[1].split(" "))
                .mapToInt(Integer::valueOf)
                .boxed()
                .sorted((o1, o2) -> Integer.compare(o2, o1))    // 큰 점수부터 정렬
                .toArray(Integer[]::new);

        final Stack<Integer> shootable = new Stack<>(); // 결과가 저장될 스택. 인형의 idx

        tryShoot(shootable, 0, 0);

        String result = shootable.stream()
                .mapToInt(offset -> SCORES[offset])
                .sorted()
                .mapToObj(n -> String.valueOf(n))
                .collect(Collectors.joining(" "));
        System.out.println("result: " + result);
    }

    /**
     * 현재점수와 이번 점수로 인형을 쏠지 말지 결정
     * @param shootable 맞추기로 결정한 인형들
     * @param offset    이번에 시도(점수를 더해볼)할 인형
     * @param score     현재까지의 점수
     */
    private static void tryShoot(Stack<Integer> shootable, int offset, int score) {
        if (score == TARGET_SCORE) {
//          System.out.println("found. stack:" + logStack(shootable) + " score:" + score);
            return;
        }

        if (score <= TARGET_SCORE && offset + 1 < SCORES.length) {  // 아직 인형을 더 쏠수 있음 & 다음 시도할 인형이 있을경우: 이번 인형은 쏘는걸로 결정
            shootable.push(offset); // 이번 인형을 스택에 넣음
//          System.out.println("stack:" + logStack(shootable) + ", push:" + SCORES[offset] + ", score:" + (score + SCORES[offset]));
            tryShoot(shootable, offset + 1, score + SCORES[offset]);    // 다음 인형을 쏠수 있는지 시도 재귀호출
        } else {    // 점수가 넘거나 다음 시도할 인형이 없음: 기존에 쏘기로 결정했던 인형을 하나 없애고 그것 다음 인형으로 시도
            if (shootable.size() < 1) {
                return;
            }

            int pop = shootable.pop();  // 이전에 결정했던 인형을 하나 없앰. 스택에서 제거
//          System.out.println("stack:" + logStack(shootable) + ", pop:" + SCORES[pop] + ", score:" + (score - SCORES[pop]));
            tryShoot(shootable, pop + 1, score - SCORES[pop]);  // 없앤 인형의 다음 인형으로 시도
        }
    }

    private static String logStack(Stack<Integer> shootable) {
        return "[" + 
                shootable.stream()
                    .mapToInt(offset -> SCORES[offset])
                    .mapToObj(n -> String.valueOf(n))
                    .collect(Collectors.joining(" ")) +
                "]";
    }

}

입력에 들어갈 숫자들은 임의로 지정해주었습니다

bool Compare(int num)
{
    for (num; num < total; num++)
    {
        if ((temp - dolls[num]) == 0)
        {
            combine.push_back(dolls[num]);
            return true;
        }

        else if ((temp - dolls[num]) > 0)
        {
            temp -= dolls[num];
            combine.push_back(dolls[num]);
            if (Compare(num + 1))
                return true;
            else
            {
                combine.pop_back();
                temp += dolls[num];
            }
        }

        else if ((temp - dolls[num]) < 0)
        {
            continue; 
        }
    }

    // num 번째 숫자에서 끝까지 돌았는데 찾지 못한 경우

    return false;
}

int main()
{
        for (int i = 0; i < total; i++)
    {
        temp = sum;
        if (Compare(i)) // 성공시 값들 출력하기
        {
            for (int i = 0; i < combine.size(); i++)
            {
                cout << combine[i] << endl;
            }
            break;
        }
        else // 실패시 계속 찾기
        {
            combine.clear();
            continue;
        }
    }
}

import java.text.*;
import java.util.*;

public class Main {
    static List<Integer>doll_num=new ArrayList<Integer>();
    static List<Integer>answers=new ArrayList<Integer>() {};

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);

        Random random=new Random();

        System.out.print("인형의 개수는? : ");
        int dolls=sc.nextInt();
        System.out.print("맞춰야 하는 총 점수는? : ");
        int sum=sc.nextInt();

        for(int i=0;i<dolls;i++) {
            int ran_num=random.nextInt(49)+1;
            if(!doll_num.contains(ran_num)) {
                doll_num.add(ran_num);
                continue;
            }i--;
        }

        Collections.sort(doll_num);

        System.out.println(doll_num);

        for(int i=0;i<doll_num.size();i++) {
            int k=i+1;

            while(k<doll_num.size()) {
                if(sum==(doll_num.get(i)+doll_num.get(k))) {
                    answers.add(doll_num.get(i));
                    answers.add(doll_num.get(k));
                }
                k++;
            }
        }

        if(answers.isEmpty()) {
            for(int i=0;i+1<doll_num.size();i++) {
                for(int k=0;k<doll_num.size();k++) {
                    if((k!=i)&&(k!=i+1)) {
                        if((sum==doll_num.get(i)+doll_num.get(i+1)+doll_num.get(k))) {
                            answers.add(doll_num.get(i));
                            answers.add(doll_num.get(i+1));
                            answers.add(doll_num.get(k));
                        }
                    }
                }
            }
        }

        Collections.sort(answers);

        System.out.println(answers);
    }
}

뭐 알아보기 쉽지 않지만 올립니다.

n,w = map(int,input().split())
arr = [int(i) for i in input().split()]
arr.sort()

stc,result = [],[]
id,cw = 0,0

while 1:
    if cw+arr[id] < w:
        stc.append(id)
        cw += arr[id]
    elif cw+arr[id] == w:
        result.append([arr[i] for i in stc]+[arr[id]])
    if not stc or stc[0] == len(arr)-1:
        if cw == w: result.append([arr[-1]])
        break
    id += 1
    while id == len(arr) and stc:
        id = stc.pop()+1
        cw = sum(arr[i] for i in stc)

print(result)

from itertools import combinations

def doll(input1, input2):
    list1 = input1.split()
    list2 = sorted(map(int,input2.split()))

    #들어온 개수 확인
    if int(list1[0]) != len(list2):
        return "인형의 개수가 올바르지 않습니다!"

    # 숫자합구하기
    temp_sum=0
    for i in range(1,len(list2)+1): #i = 1,2,3,4,...10
        com = combinations(list2,i)
        for c in com:
            if sum(c) == int(list1[1]):
                return c

    return "불가능!"

print(doll(input(),input()))

Combination 함수를 알고 암이 나았습니다 ㅎㅎ

class Doll:
    def __init__(self, data, number, _sum):
        self.data = data
        self.n = number
        self.s = _sum

    def search(self, dolls=[], idx=0):            
        if sum(dolls) > self.s:
            return
        if sum(dolls) == self.s:
            print(sorted(dolls))
            raise NotImplementedError
        if idx >= self.n:
            return

        temp = dolls[:]
        self.search(temp, idx+1)
        temp.append(self.data[idx])
        self.search(temp, idx+1)

    def find(self):
        try:
            self.search()
            print('정답을 찾지 못했습니다.')
        except NotImplementedError:
            pass


n, s = map(int, input().split(' '))
data = list(map(int, input().split(' ')))

P = Doll(data, n, s)
P.find()

13 70
7 18 15 27 3 14 6 15 9 30 21 13 25
[15, 25, 30]

import java.util.ArrayList; import java.util.List; import java.util.Scanner;

public class sol122 {

static int sum = 50;

static int doll[]  = {25, 27, 3, 12, 6, 15, 9, 30, 21, 19};
static boolean used[] = new boolean[doll.length];

static List<List<Integer>> patterns;

// current를 추가함으로써 중복 방지
public static void choose(int count, int current, ArrayList<Integer> pattern) {

    if(sum == count) {
        patterns.add(new ArrayList<>(pattern));
        return;
    }

    for(int i=current; i<doll.length; i++) {
        if(used[i]) continue;

        used[i] = true;
        pattern.add(doll[i]);
        choose(count+doll[i], i, pattern);

        used[i] = false;
        pattern.remove(pattern.size()-1);

    }
}

public static void main(String[] args) throws Exception {

    Scanner sc = new Scanner(System.in);


    patterns = new ArrayList<>();

    choose(0, 0, new ArrayList<Integer>());

    for(int i=0; i<patterns.size(); i++) {
        List temp = patterns.get(i);

        for(int j=0; j<temp.size(); j++) {
            System.out.print(temp.get(j) + " ");
        }
        System.out.println();
    }



}

}

#인형의 갯수와 합을 넣으면, 합 이하의 숫자들이 랜덤으로 생성됩니다
#그 중 합이 입력한 합과 동일한 리스트를 출력합니다

from random import *

def conv(x,n):
    result=[]
    while(x>=n):
        if x%n not in result:
            result.append(x%n)
        x=x//n
    if x not in result:
        result.append(x)
    return (result)   

temp=str(input('인형갯수?  숫자의 합?')).split(' ')
n,numsum=int(temp[0]),int(temp[1])

num=[]
for i in range (n):
    num.append(randint(0,numsum-1))
print ('인형리스트 : ',num)

sum_list=[]
for i in range (0,n**4):
    temp,sum,doll_num_list=conv(i,n),0,[]

    for j in range (len(temp)):
        doll_num=num[temp[j]]
        sum+=doll_num
        doll_num_list.append(doll_num)

    if sum==numsum:
        doll_num_list.sort()
        if doll_num_list not in sum_list:
            sum_list.append(doll_num_list)

print ('\n합이',numsum,'인 리스트 : ',sum_list)

import itertools
while True:
    dnrnlst=list(map(int,input("인형의 개수와 인형 획득에 필요한 숫자의 합을 입력하십시오: ").split(" ")))
    dn,rn=dnrnlst[0],dnrnlst[1]
    if len(dnrnlst)==2:
        while True:
            dnlst=list(map(int,input("인형에 쓰인 숫자들을 입력하십시오: ").split(" ")))
            if len(dnlst)==dn:
                break
            else:
                print("숫자들이 인형의 개수와 불일치 합니다. 다시 입력하십시오. 인형의 개수: "+str(dn))
        break
    else:
        print("잘못입력하셨습니다. 다시 입력하십시오.")
i=1
while i<=dn:
    for c in itertools.combinations(dnlst,i):
        if sum(c)==rn:
            print(sorted(list(c)))
        else:
            continue
    i+=1

결과

input1: 10 50
input2: 25 27 3 12 6 15 9 30 21 19
output: [6, 19, 25]

from itertools import combinations

items = [x for x in input("인형 각각에 쓰여진 숫자를 입력 : ").split()]
num = int(input("인형의 필요한 합 : "))

for i in range(1,len(items)+1):
    a = list(combinations(items,i))
    for j in a:
        total = 0
        for k in j:
            total+=int(k)
        if total == num:
            r=[]
            for w in j:  # 오름차순 
                r.append(int(w))
                r.sort()
            print(r)

// Rust

// 재귀로 풀었습니다

fn sum_num() {

let vec = vec![3,6,9,12,15,19,21,25,27,30];
let sum = 50;
for i in 2..10 {
    if let Some(res) = f(i, &vec[..], sum) {
        println!("sum of {:?} = {}", res, sum);
    }    
}

} fn f(n: usize, arr: &[usize], sum:usize) -> Option> {

if n == 1 { return f1(arr, sum);}

let l = arr.len();
let mut result = vec![];
for i in 0..(l-(n-1)) {
    let d = arr[i];
    if d > sum { continue; }
    if let Some(res) = f(n-1, &arr[i+1..], sum-d) {
        result.push(d);
        result.extend(res);}
}
if result != vec![] { Some(result) }
else {None}

} fn f1(arr: &[usize], sum: usize) -> Option> {

let l = arr.len();
assert!(l > 0);

let mut result = vec![];
if arr.contains(&sum) { result.push(sum); }
if result != vec![] { Some(result) }
else {None}

}