子集的Java算法解决方案 [英] a Java algorithm solution for subsets

问题描述

公共类解决方案{公共 ArrayList>子集(int [] num){ArrayList>结果 = new ArrayList>();if(num == null || num.length == 0) {返回结果；}ArrayList<整数>list = new ArrayList();Arrays.sort(num);子集助手(结果，列表，数量，0)；返回结果；}私有无效子集Helper(ArrayList>结果，ArrayList<整数>list, int[] num, int pos) {//特别是，这些变量代表什么result.add(new ArrayList(list));for (int i = pos; i 

<块引用>

说明
给定一组不同的整数，返回所有可能的子集.

通知
子集中的元素必须按非降序排列.解决方案集不得包含重复的子集.你有没有遇到过这个问题真正的面试?是的

示例
如果 S = [1,2,3]，则解为:

<预><代码>[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]

我无法理解没有单一注释的答案背后的逻辑，谁能提供详细的注释，谢谢您的时间！

解决方案

注意:评论框太小.所以把答案放在这里.只是不要......投票.

<块引用>

@KarelG 谢谢.. 这个函数中的变量是什么意思?私有无效子集Helper(ArrayList> 结果，ArrayList 列表，int[] num，int pos)

那个 private void ... 是一个方法签名，而不是注释".方法签名由各个部分组成.您可以在此链接 上阅读有关此主题的更多信息><块引用>

更一般地说，方法声明有六个组成部分，依次为:

1) 修饰符——例如 public、private 以及您稍后将了解的其他修饰符.

2) 返回类型——方法返回值的数据类型，如果方法没有返回值，则为void.

3) 方法名——字段名的规则也适用于方法名，但约定略有不同.

4) 括号中的参数列表——以逗号分隔的输入参数列表，前面是它们的数据类型，用括号 () 括起来.如果没有参数，则必须使用空括号.

5) 例外列表——稍后讨论.

6) 方法主体，括在大括号之间——方法的代码，包括局部变量的声明，放在这里.

现在，您已经要求变量"(参数实际上是正确的术语)，其中有 4 个:ArrayList>结果, ArrayListlist、int[] num 和 int pos.其实按照方法一步一步来就可以搞定了.

你看到的是递归.该方法在 for 循环期间调用自身，重用代码.(请用笔和纸，结合例子一步一步做，你就明白了)

第一个 result 顾名思义，一个包含结果的动态数组(又名列表).在操作结束时，此变量应具有与示例中解决方案"块中描述的相同的数据.正在此方法中修改此数组.

然后 list 是一个列表，在递归过程中由 num 数组中存在的值填充.num 是您的数组，即 S = [1,2,3].因此 num === S.

最后，pos 是 num 数组的索引以选择其元素.在 for 循环中，您可以看到该索引用于填充 list(参见 list.add(num[i]); ).

开始时，当第一次调用 subsetsHelper 时，num 为 0.循环运行 3 次，从 0..2 (subsetsHelper 会使用新值调用.例如，在您的 for 循环第一次运行时，subsetsHelper 被调用，并使用以下值:

1. result -> 与调用方法时相同的 result 列表，但更新为空列表 result.add(new ArrayList;(list)) 因为它是在 for 循环之前执行的.
2. list -> 更新为 list.add(num[i]);，一个来自 S 的值，其中 i = pos(在 for 循环内执行)
3. num -> 与初始数组相同(因此为 S).你可以看到在这个方法中它没有被改变.
4. pos -> 自 i + 1 执行后更新(这次，pos 为 1).

然后继续按照步骤操作，直到返回主函数.

只需拿起笔和纸，按照方法体中的语句一步一步来.你最终会弄明白的.

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!

解决方案

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.

这篇关于子集的Java算法解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！