How to find non duplicate set of integer from an array that equals to the target?

This is an interv开发者_如何学JAVAiew question.

Given an array of integers and an integer target, find all combinations which sum up to target. Don't output duplicates. e.g., [2,3,4], target is 5. then output should be [2,3], or [3,2], but not both.

If I understand correctly, this is the subset sum problem.

Quoting from wikipedia's subset sum problem:

An equivalent problem is this: given a set of integers and an integer s, does any non-empty subset sum to s?

In python

>>> L=[2,3,4]
>>> from itertools import combinations
>>> for i in range(len(L)):
...     for j in combinations(L,i):
...         if sum(j) == 5:
...             print j
... 
(2, 3)

It looks like knapsack problem which is np-complete hence probably there doesn't exist an effective algorithm for solve this problem.