v0rtex's blog

Minimum subset size for target sum.
By v0rtex, history, 4 years ago, In English

An array of size N is given and a value K. You have to find the minimum subset size so that subset sum is exactly equal to K, if not print -1. 0 < K, a[i], N < 10^6.

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
4 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Isn't this the famous coin change problem? You can easily find the solution online.

→ Reply
  • »
    »
    4 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +8 Vote: I do not like it

    Sorry, can you explain how?

    In problem which mentioned in post constraints for $$$N, K, a_i$$$ to high for stupid knapsack.

    Other solution with sqrt opt works $$$O(n * log(max(a_i)) * sqrt(K))$$$, thats too much.

    → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      This problem came in Colortoken placement exam. Can you please tell me how can it be solved?

      → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Could you elaborate on this sqrt optmization (or provide links)? Depending on what it is maybe the solution is using it with bitset

      → Reply
      • »
        »
        »
        »
        7 weeks ago, hide # ^ |
        ← Rev. 4  
        Vote: I like it 0 Vote: I do not like it

        Sorry for necroposting, but here's my solution:

        Consider an element $$$e$$$ with count $$$x$$$. Insert values $$$e, 2\cdot e, 4\cdot e, ... $$$ etc, with weight (the number of element inserted) as $$$1, 2, 4, ...$$$ while it's still doable ($$$2^k \leq x$$$). Insert $$$x\cdot e$$$ after that (if $$$x \gt 0$$$) the same way. By the sqrt-log theorem for knapsack problems ($$$\sum{\log(x)} \in O(\sqrt{\sum{a_i}})$$$), we got the total TC to be $$$O(K \sqrt{\sum{a_i}})$$$.

        → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      Or can't we do fft here? Binary search on no of boxes. Complexity will be $$$O(N*logN*log(max a_i))$$$

      → Reply
      • »
        »
        »
        »
        4 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        How do you check that you can collect this amount or not by FFT with fixed amount of items?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, hide # ^ |
           
          Vote: I like it -18 Vote: I do not like it

          I mean Like we do "Fast subset transform" in a similar way if possible lets say $$$s$$$ will be the smallest size of some subset such that it's sum is $$$K$$$. then polynomial raise to power $$$s$$$ will contains non-zero coefficient for $$$x^K$$$ term right.

          → Reply
»
4 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I encountered a similar problem recently, can someone suggest some solution:
Given an array A of size N, find the number of subsets of size exactly K that add up to S.
e.g: 

A = [1,1,1,2,3,4]
K=3, S=6
answer: 6

explanation (0 based indexing)

[0,1,5]
[0,2,5]
[1,2,5]
[0,3,4]
[1,3,4]
[2,3,4]

I don't remember the constraints, but let's say 1 <= N,S <= 1000

and would it really be possible to solve under normal time-limits i.e. 1 or 2 sec if N,S were 10^5?

→ Reply