CODEWITHSUNDEEP
algorithm
q0987
q0987

Reputation: 35982

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

This is an interview 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.

Upvotes: 1

Views: 437

Answers (3)

Ishtar
Ishtar

Reputation: 11662

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?

Upvotes: 3

John La Rooy
John La Rooy

Reputation: 304147

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)

Upvotes: 2

ninjaaa
ninjaaa

Reputation: 293

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

Upvotes: 1

Related Questions