Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

a Java algorithm solution for subsets

public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(num == null || num.length == 0) {
            return result;
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        Arrays.sort(num);  
        subsetsHelper(result, list, num, 0);

        return result;
    }


    private void subsetsHelper(ArrayList<ArrayList<Integer>> result,
        ArrayList<Integer> list, int[] num, int pos) {//especially,what are these variable represent for

        result.add(new ArrayList<Integer>(list));

        for (int i = pos; i < num.length; i++) {

            list.add(num[i]);
            subsetsHelper(result, list, num, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

Description
Given a set of distinct integers, return all possible subsets.

Notice
Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. Have you met this question in a real interview? Yes

Example
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

I could not understand the logic behind the answer which has no single annotation,could someone offer detailed annotation,thank you for your time!

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

note: comment box is too small. So putting the answer here. Just don't ... vote.

@KarelG thank you.. what are variables in this function mean? private void subsetsHelper(ArrayList> result, ArrayList list, int[] num, int pos)

That private void ... is a method signature, not "annotation". A method signature consists of various parts. You can read more on this topic on this link

More generally, method declarations have six components, in order:

1) Modifiers—such as public, private, and others you will learn about later.

2) The return type—the data type of the value returned by the method, or void if the method does not return a value.

3) The method name—the rules for field names apply to method names as well, but the convention is a little different.

4) The parameter list in parenthesis—a comma-delimited list of input parameters, preceded by their data types, enclosed by parentheses, (). If there are no parameters, you must use empty parentheses.

5) An exception list—to be discussed later.

6) The method body, enclosed between braces—the method's code, including the declaration of local variables, goes here.

Now, you've asked for the "variables" (parameters is actually the right term), well there are 4 of them: ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, int[] num and int pos. In fact, you would be able to figure it out if you follow the method step by step.

What you see is a recursion. The method calls itself during the for loop, reusing the code. (please, use pen and paper and do it step by step with the example. you will understand it)

The first result is what the name says, a dynamic array (aka list) that contains the result. At the end of the operation, this variable should have same data as described in the "solution" block in your example. This array is being modified in this method.

Then list is a list being populated by values present in num array during the recursion. The num is your array, that S = [1,2,3]. Thus num === S.

finally, pos is then an index for the num array to pick its element. In the for loop, you can see that this index is used to populate the list ( see at list.add(num[i]); ).

At start, when subsetsHelper is called for the first time, num is 0. The loop runs three times, from 0..2 (< S.length). During each loop run, subsetsHelper is called with new values. Eg at the first run of your for-loop, subsetsHelper is called with the following values:

  1. result -> just the same result list as when the method is called, but updated with an empty list result.add(new ArrayList<Integer>(list)) because this got executed before the for-loop.
  2. list -> updated with list.add(num[i]);, a value from S where i = pos (executed inside the for-loop)
  3. num -> same array as initial (thus S). You can see that it doesn't get changed in this method.
  4. pos -> updated since i + 1 is executed (this time, pos is then 1).

Then just continue following the steps until you return to the main function.

Just take a pen and paper and follow the statements in the method body step by step. You will figure it out eventually.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...