Ggtcf

Start making guitar arrangements

Non-trope happy ending?

Can I sign legal documents with a smiley face?

Do Legal Documents Require Signing In Standard Pen Colors?

Character escape sequences for ">"

Where does the bonus feat in the cleric starting package come from?

If a character has darkvision, can they see through an area of nonmagical darkness filled with lightly obscuring gas?

Closed-form expression for certain product

Count the occurrence of each unique word in the file

Aragorn's "guise" in the Orthanc Stone

Problem with TransformedDistribution

Argument list too long when zipping large list of certain files in a folder

Is the U.S. Code copyrighted by the Government?

Electoral considerations aside, what are potential benefits, for the US, of policy changes proposed by the tweet recognizing Golan annexation?

Should I outline or discovery write my stories?

A social experiment. What is the worst that can happen?

Create all possible words using a set or letters

Calculating Wattage for Resistor in High Frequency Application?

Is there a working SACD iso player for Ubuntu?

Melting point of aspirin, contradicting sources

Why is so much work done on numerical verification of the Riemann Hypothesis?

What prevents the use of a multi-segment ILS for non-straight approaches?

Is it possible to have a strip of cold climate in the middle of a planet?

250 Floor Tower

Problems in recursively generating subset

What is tail recursion?How to generate a random alpha-numeric string?How do I generate random integers within a specific range in Java?How can I generate an MD5 hash?How to create a generic array in Java?Generating all permutations of a given stringWhy is `[` better than `subset`?Algorithm to generate a subset in order of its sumAlgorithm for selecting subset satisfying conditionsHow to handle subset containing an even number of elements?(Find peak problem using divide and conquer)

1

So, the algorithm generates subsets of set A by using a parameter i to refer to A[i], at each step, there are two calls, one including A[i] and other excluding A[i].
Search stops when i==n.

So, that makes sense but I can't understand what the last statement does here..

void search(int i, ArrayList<Integer> subset,ArrayList<Integer> A, int n)
 if (i==n) System.out.println(subset);
 else
 search(i+1,subset,A,n);
 subset.add(A.get(i));
 search(i+1,subset,A,n);
 subset.remove(subset.size()-1); /*Why do we need to do this? I am not making any function call after this*/
 

I tried excluding the last statement, but then it repeats elements in subsets. What's the use of the last statement?

java algorithm subset

share|improve this question

asked Mar 8 at 4:58

Little_idiotLittle_idiot

113

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Are you trying to generate subsets using backtracking?
  
  – uneq95
  Mar 8 at 5:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @uneq95 yes, i know this isn't the most efficient method.
  
  – Little_idiot
  Mar 8 at 5:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @MBo has the right answer for you
  
  – uneq95
  Mar 8 at 5:16
  

  
  
  
  

add a comment | 

1

So, the algorithm generates subsets of set A by using a parameter i to refer to A[i], at each step, there are two calls, one including A[i] and other excluding A[i].
Search stops when i==n.

So, that makes sense but I can't understand what the last statement does here..

void search(int i, ArrayList<Integer> subset,ArrayList<Integer> A, int n)
 if (i==n) System.out.println(subset);
 else
 search(i+1,subset,A,n);
 subset.add(A.get(i));
 search(i+1,subset,A,n);
 subset.remove(subset.size()-1); /*Why do we need to do this? I am not making any function call after this*/
 

I tried excluding the last statement, but then it repeats elements in subsets. What's the use of the last statement?

java algorithm subset

share|improve this question

asked Mar 8 at 4:58

Little_idiotLittle_idiot

113

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Are you trying to generate subsets using backtracking?
  
  – uneq95
  Mar 8 at 5:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @uneq95 yes, i know this isn't the most efficient method.
  
  – Little_idiot
  Mar 8 at 5:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @MBo has the right answer for you
  
  – uneq95
  Mar 8 at 5:16
  

  
  
  
  

add a comment | 

So, the algorithm generates subsets of set A by using a parameter i to refer to A[i], at each step, there are two calls, one including A[i] and other excluding A[i].
Search stops when i==n.

So, that makes sense but I can't understand what the last statement does here..

void search(int i, ArrayList<Integer> subset,ArrayList<Integer> A, int n)
 if (i==n) System.out.println(subset);
 else
 search(i+1,subset,A,n);
 subset.add(A.get(i));
 search(i+1,subset,A,n);
 subset.remove(subset.size()-1); /*Why do we need to do this? I am not making any function call after this*/
 

I tried excluding the last statement, but then it repeats elements in subsets. What's the use of the last statement?

java algorithm subset

share|improve this question

asked Mar 8 at 4:58

Little_idiotLittle_idiot

113

void search(int i, ArrayList<Integer> subset,ArrayList<Integer> A, int n)
 if (i==n) System.out.println(subset);
 else
 search(i+1,subset,A,n);
 subset.add(A.get(i));
 search(i+1,subset,A,n);
 subset.remove(subset.size()-1); /*Why do we need to do this? I am not making any function call after this*/
 

share|improve this question

asked Mar 8 at 4:58

Little_idiotLittle_idiot

113

share|improve this question

asked Mar 8 at 4:58

Little_idiotLittle_idiot

113

asked Mar 8 at 4:58

Little_idiotLittle_idiot

113

asked Mar 8 at 4:58

Little_idiotLittle_idiot

113

1 Answer
1

active

oldest

votes

2

You have the only instance of subset shared at all levels of recursion.

So after using item you should return to lower level with the same state of subset.

Imagine call tree

[]
 []
 [2] *

[1] 
 [1]
 [1 2]

After you made subset [2] (code point *), you return to the first level and must generate subset [1]. But subset object already contains item 2, so generation of [1] is impossible without deleting item 2 in *

---

If implementation creates new copy of argument, you don't need to restore state.

share|improve this answer

edited Mar 8 at 17:11

answered Mar 8 at 5:06

MBoMBo

49.7k23051

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Sorry, didn't get that, I mean initially subset =[ ], when I am calling search for first time, I am sharing [ ], then subset = [ A[0] ], and I am using this instance aka [ A[0] ], why do I need to remove A[0] and make subset = [ ] , again? I am not making any function call after that, where am I sharing that instance?
  
  – Little_idiot
  Mar 8 at 5:23
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  ArrayList<Integer> subset argument is really address of object. Only one copy of object does exist (if you don't make deep copy). When you modify object at deeper recursion level, changes will be seen at higher levels too. I added example.
  
  – MBo
  Mar 8 at 5:56
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Little_idiot Are you aware about marking answers as solution?
  
  – MBo
  Mar 8 at 17:11
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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/3.0/"u003ecc by-sa 3.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
);



);

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%2fstackoverflow.com%2fquestions%2f55056974%2fproblems-in-recursively-generating-subset%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

You have the only instance of subset shared at all levels of recursion.

So after using item you should return to lower level with the same state of subset.

Imagine call tree

[]
 []
 [2] *

[1] 
 [1]
 [1 2]

After you made subset [2] (code point *), you return to the first level and must generate subset [1]. But subset object already contains item 2, so generation of [1] is impossible without deleting item 2 in *

---

If implementation creates new copy of argument, you don't need to restore state.

share|improve this answer

edited Mar 8 at 17:11

answered Mar 8 at 5:06

MBoMBo

49.7k23051

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Sorry, didn't get that, I mean initially subset =[ ], when I am calling search for first time, I am sharing [ ], then subset = [ A[0] ], and I am using this instance aka [ A[0] ], why do I need to remove A[0] and make subset = [ ] , again? I am not making any function call after that, where am I sharing that instance?
  
  – Little_idiot
  Mar 8 at 5:23
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  ArrayList<Integer> subset argument is really address of object. Only one copy of object does exist (if you don't make deep copy). When you modify object at deeper recursion level, changes will be seen at higher levels too. I added example.
  
  – MBo
  Mar 8 at 5:56
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Little_idiot Are you aware about marking answers as solution?
  
  – MBo
  Mar 8 at 17:11
  

  
  
  
  

add a comment | 

2

You have the only instance of subset shared at all levels of recursion.

So after using item you should return to lower level with the same state of subset.

Imagine call tree

[]
 []
 [2] *

[1] 
 [1]
 [1 2]

After you made subset [2] (code point *), you return to the first level and must generate subset [1]. But subset object already contains item 2, so generation of [1] is impossible without deleting item 2 in *

---

If implementation creates new copy of argument, you don't need to restore state.

share|improve this answer

edited Mar 8 at 17:11

answered Mar 8 at 5:06

MBoMBo

49.7k23051

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Sorry, didn't get that, I mean initially subset =[ ], when I am calling search for first time, I am sharing [ ], then subset = [ A[0] ], and I am using this instance aka [ A[0] ], why do I need to remove A[0] and make subset = [ ] , again? I am not making any function call after that, where am I sharing that instance?
  
  – Little_idiot
  Mar 8 at 5:23
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  ArrayList<Integer> subset argument is really address of object. Only one copy of object does exist (if you don't make deep copy). When you modify object at deeper recursion level, changes will be seen at higher levels too. I added example.
  
  – MBo
  Mar 8 at 5:56
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Little_idiot Are you aware about marking answers as solution?
  
  – MBo
  Mar 8 at 17:11
  

  
  
  
  

add a comment | 

You have the only instance of subset shared at all levels of recursion.

So after using item you should return to lower level with the same state of subset.

Imagine call tree

[]
 []
 [2] *

[1] 
 [1]
 [1 2]

After you made subset [2] (code point *), you return to the first level and must generate subset [1]. But subset object already contains item 2, so generation of [1] is impossible without deleting item 2 in *

---

If implementation creates new copy of argument, you don't need to restore state.

share|improve this answer

edited Mar 8 at 17:11

answered Mar 8 at 5:06

MBoMBo

49.7k23051

[]
 []
 [2] *

[1] 
 [1]
 [1 2]

share|improve this answer

edited Mar 8 at 17:11

answered Mar 8 at 5:06

MBoMBo

49.7k23051

answered Mar 8 at 5:06

MBoMBo

49.7k23051

answered Mar 8 at 5:06

MBoMBo

49.7k23051