Mfcttrf

Maze generator & animator in Python

Owner keeps cutting corners and poaching workers for his other company

What is the difference between a translation and a Galilean transformation?

What should I do about my non-English publications when applying to a University in an English-speaking country?

Does the 2019 UA artificer need to prepare the Lesser Restoration spell to cast it with their Alchemical Mastery feature?

Why do the British opposition parties not want a new election?

How is lower/no gravity simulated on a planet with gravity, without leaving the surface?

What makes things real?

How can I finish my PhD?

Are personality traits, ideals, bonds, and flaws required?

If every star in the universe except the Sun were destroyed, would we die?

My favorite color is blue what is your favorite color?

Bit floating sequence

Why would an airport be depicted with symbology for runways longer than 8,069 feet even though it is reported on the sectional as 7,200 feet?

The pirate treasure of Leatherback Atoll

Why do we capitalize the word "Uzi"?

When calculating averages, why can we treat exploding die as if they're independent?

Chandrayaan 2: Why is Vikram Lander's life limited to 14 Days?

Is gravity a factor for sustaining fusion?

A PEMDAS issue request for explanation

When does order matter in probability?

Are programming languages necessary/useful for operations research practitioner?

Aftermarket seats

Why was "leaping into the river" a valid trial outcome to prove one's innocence?

Algorithm to count the number of subsets of size k with sum of all its elements minimum possible

Find vectors with elements of finite fields that sum up to given valueefficient cumulative all over combinations of boolean vector elementsFinding a maximum-weight base of a a matroid, in reverseGet a fixed-size family of k-element subsetsNo. of subsets whose element multiply to give a square numberSum of unique elements in all sub-arrays of an arrayWhat is the fastest algorithm of generating all possible permutations (within a given set of constraints) of a multidimensional array?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

2

$begingroup$

An array is given eg:-1 2 2 2 and we need to count the number of subsets for it of size k which has the sum of elements minimum possible

here the subsets of size k=3 are:-
122
122
122
222

we see that there are 3 subsets having the minimum sum

I did this in bruteforce approach..first I stored the subsets of size k in a vector and then found the sum for each of the subsets and stored them in another vector and then counted the frequency of the minimum element

how to optimize it?

combinatorics

share|cite|improve this question

asked 8 hours ago

ANKIT SINGHAANKIT SINGHA

1111 bronze badge

New contributor

ANKIT SINGHA is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

2

$begingroup$

An array is given eg:-1 2 2 2 and we need to count the number of subsets for it of size k which has the sum of elements minimum possible

here the subsets of size k=3 are:-
122
122
122
222

we see that there are 3 subsets having the minimum sum

I did this in bruteforce approach..first I stored the subsets of size k in a vector and then found the sum for each of the subsets and stored them in another vector and then counted the frequency of the minimum element

how to optimize it?

combinatorics

share|cite|improve this question

asked 8 hours ago

ANKIT SINGHAANKIT SINGHA

1111 bronze badge

New contributor

ANKIT SINGHA is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

$begingroup$

An array is given eg:-1 2 2 2 and we need to count the number of subsets for it of size k which has the sum of elements minimum possible

here the subsets of size k=3 are:-
122
122
122
222

we see that there are 3 subsets having the minimum sum

I did this in bruteforce approach..first I stored the subsets of size k in a vector and then found the sum for each of the subsets and stored them in another vector and then counted the frequency of the minimum element

how to optimize it?

combinatorics

share|cite|improve this question

asked 8 hours ago

ANKIT SINGHAANKIT SINGHA

1111 bronze badge

New contributor

ANKIT SINGHA is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

asked 8 hours ago

ANKIT SINGHAANKIT SINGHA

1111 bronze badge

New contributor

ANKIT SINGHA is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

asked 8 hours ago

ANKIT SINGHAANKIT SINGHA

1111 bronze badge

New contributor

ANKIT SINGHA is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 8 hours ago

ANKIT SINGHAANKIT SINGHA

1111 bronze badge

New contributor

ANKIT SINGHA is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 8 hours ago

ANKIT SINGHAANKIT SINGHA

1111 bronze badge

2 Answers
2

active

oldest

votes

1

$begingroup$

Suppose that you arrange the array in non-decreasing order. It's not hard to check that the minimum sum is obtained by taking the first $k$ elements.

Suppose that the distinct values found in the array are $a_1 < a_2 < cdots$, where $a_i$ appears $n_i$ times. There is an index $d$ such that $n_1 + cdots + n_d-1 < k$ but $n_1 + cdots + n_d geq k$. Thus every $k$-subset of minimum sum contains all elements of values $a_1,ldots,a_d-1$, and any $k-(n_1+cdots+n_d-1)$ elements of value $a_d$. You take it from here.

share|cite|improve this answer

answered 8 hours ago

Yuval FilmusYuval Filmus

207k1515 gold badges200200 silver badges368368 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  could you please elaborate it more clearly with an example,would appreciate that!
  $endgroup$
  – ANKIT SINGHA
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It’s better if you worked it out on your own.
  $endgroup$
  – Yuval Filmus
  7 hours ago
  

  
  
  
  

add a comment | 

0

$begingroup$

There are 3 minimum subsets, which happens to be the same number as the largest number in the sum. Can you play around with this insight to see if you can find out how to solve it?

For example, if the minimum sum contains both (e.g.) the numbers 5 and 7, then realize that all 5ers have to be included in every minimum sum!

share|cite|improve this answer

answered 8 hours ago

Pål GDPål GD

7,3952323 silver badges4242 bronze badges

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

ANKIT SINGHA is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f113537%2falgorithm-to-count-the-number-of-subsets-of-size-k-with-sum-of-all-its-elements%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

Suppose that you arrange the array in non-decreasing order. It's not hard to check that the minimum sum is obtained by taking the first $k$ elements.

Suppose that the distinct values found in the array are $a_1 < a_2 < cdots$, where $a_i$ appears $n_i$ times. There is an index $d$ such that $n_1 + cdots + n_d-1 < k$ but $n_1 + cdots + n_d geq k$. Thus every $k$-subset of minimum sum contains all elements of values $a_1,ldots,a_d-1$, and any $k-(n_1+cdots+n_d-1)$ elements of value $a_d$. You take it from here.

share|cite|improve this answer

answered 8 hours ago

Yuval FilmusYuval Filmus

207k1515 gold badges200200 silver badges368368 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  could you please elaborate it more clearly with an example,would appreciate that!
  $endgroup$
  – ANKIT SINGHA
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It’s better if you worked it out on your own.
  $endgroup$
  – Yuval Filmus
  7 hours ago
  

  
  
  
  

add a comment | 

1

$begingroup$

Suppose that you arrange the array in non-decreasing order. It's not hard to check that the minimum sum is obtained by taking the first $k$ elements.

Suppose that the distinct values found in the array are $a_1 < a_2 < cdots$, where $a_i$ appears $n_i$ times. There is an index $d$ such that $n_1 + cdots + n_d-1 < k$ but $n_1 + cdots + n_d geq k$. Thus every $k$-subset of minimum sum contains all elements of values $a_1,ldots,a_d-1$, and any $k-(n_1+cdots+n_d-1)$ elements of value $a_d$. You take it from here.

share|cite|improve this answer

answered 8 hours ago

Yuval FilmusYuval Filmus

207k1515 gold badges200200 silver badges368368 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  could you please elaborate it more clearly with an example,would appreciate that!
  $endgroup$
  – ANKIT SINGHA
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It’s better if you worked it out on your own.
  $endgroup$
  – Yuval Filmus
  7 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

Suppose that you arrange the array in non-decreasing order. It's not hard to check that the minimum sum is obtained by taking the first $k$ elements.

Suppose that the distinct values found in the array are $a_1 < a_2 < cdots$, where $a_i$ appears $n_i$ times. There is an index $d$ such that $n_1 + cdots + n_d-1 < k$ but $n_1 + cdots + n_d geq k$. Thus every $k$-subset of minimum sum contains all elements of values $a_1,ldots,a_d-1$, and any $k-(n_1+cdots+n_d-1)$ elements of value $a_d$. You take it from here.

share|cite|improve this answer

answered 8 hours ago

Yuval FilmusYuval Filmus

207k1515 gold badges200200 silver badges368368 bronze badges

$endgroup$

share|cite|improve this answer

answered 8 hours ago

Yuval FilmusYuval Filmus

207k1515 gold badges200200 silver badges368368 bronze badges

answered 8 hours ago

Yuval FilmusYuval Filmus

207k1515 gold badges200200 silver badges368368 bronze badges

answered 8 hours ago

Yuval FilmusYuval Filmus

207k1515 gold badges200200 silver badges368368 bronze badges

0

$begingroup$

There are 3 minimum subsets, which happens to be the same number as the largest number in the sum. Can you play around with this insight to see if you can find out how to solve it?

For example, if the minimum sum contains both (e.g.) the numbers 5 and 7, then realize that all 5ers have to be included in every minimum sum!

share|cite|improve this answer

answered 8 hours ago

Pål GDPål GD

7,3952323 silver badges4242 bronze badges

$endgroup$

add a comment | 

0

$begingroup$

There are 3 minimum subsets, which happens to be the same number as the largest number in the sum. Can you play around with this insight to see if you can find out how to solve it?

For example, if the minimum sum contains both (e.g.) the numbers 5 and 7, then realize that all 5ers have to be included in every minimum sum!

share|cite|improve this answer

answered 8 hours ago

Pål GDPål GD

7,3952323 silver badges4242 bronze badges

$endgroup$

add a comment | 

$begingroup$

There are 3 minimum subsets, which happens to be the same number as the largest number in the sum. Can you play around with this insight to see if you can find out how to solve it?

For example, if the minimum sum contains both (e.g.) the numbers 5 and 7, then realize that all 5ers have to be included in every minimum sum!

share|cite|improve this answer

answered 8 hours ago

Pål GDPål GD

7,3952323 silver badges4242 bronze badges

$endgroup$

share|cite|improve this answer

answered 8 hours ago

Pål GDPål GD

7,3952323 silver badges4242 bronze badges

answered 8 hours ago

Pål GDPål GD

7,3952323 silver badges4242 bronze badges

answered 8 hours ago

Pål GDPål GD

7,3952323 silver badges4242 bronze badges