英文:
Java: Recursive function not generating power set of a set
问题
我正在尝试基于给定整数集合生成幂集（所有可能的子集）。我试图使用递归，基于这样的原理：主集合中的每个元素可以在子集中，也可以不在子集中。然而，当我在示例集合 {1, 5, 11, 5} 上运行我的函数时，我错过了一些子集，例如 {1, 5, 5}。以下是我的 Java 代码：
// 生成给定集合 S 的幂集的函数
public static void determinePowerSet(int[] baseSet, List<Integer> currSet, int index, int sum)
{
// 如果当前索引在末尾，表示我们已经生成完所有子集
if (index == baseSet.length) {
return;
}
// 在列表中添加当前元素的子集
List<Integer> addToSet = new LinkedList<Integer>(currSet);
addToSet.add(baseSet[index]);
// 不将当前元素添加到集合中
determinePowerSet(baseSet, currSet, index + 1, sum);
// 将当前元素添加到集合中
determinePowerSet(baseSet, addToSet, index + 1, sum + baseSet[index]);
}
public static void main(String[] args)
{
determinePowerSet(new int[] {1, 5, 11, 5}, new LinkedList<Integer>(), 0, 0);
}
以下是函数调用的输出：
sum = 0, currSet = [], index = 0
sum = 0, currSet = [], index = 1
sum = 0, currSet = [], index = 2
sum = 0, currSet = [], index = 3
sum = 11, currSet = [11], index = 3
sum = 5, currSet = [5], index = 2
sum = 5, currSet = [5], index = 3
sum = 16, currSet = [5, 11], index = 3
sum = 1, currSet = [1], index = 1
sum = 1, currSet = [1], index = 2
sum = 1, currSet = [1], index = 3
sum = 12, currSet = [1, 11], index = 3
sum = 6, currSet = [1, 5], index = 2
sum = 6, currSet = [1, 5], index = 3
sum = 17, currSet = [1, 5, 11], index = 3
英文:
I am trying to generate a power set (all possible subsets) of integers based on a given set of integers. I am trying to use recursion based on the principle that each element in the master set can be in a subset or not in a subset. However, when I run my function on the example set {1, 5, 11, 5}, I am missing subsets, such as {1, 5, 5}. Below is my Java code:
// Function to generate power set of given set S
public static void determinePowerSet(int[] baseSet, List<Integer> currSet, int index, int sum)
{
// If the current index is at the end, we've finished generating subsets
if (index == baseSet.length) {
return;
}
// The subset in which we add the current element in the list
List<Integer> addToSet = new LinkedList<Integer>(currSet);
addToSet.add(baseSet[index]);
// Do not add the current element to the set
determinePowerSet(baseSet, currSet, index + 1, sum);
// Add the current element to the set
determinePowerSet(baseSet, addToSet, index + 1, sum + baseSet[index]);
}
public static void main(String[] args)
{
determinePowerSet(new int[] {1, 5, 11, 5}, new LinkedList<Integer>(), 0, 0);
}
Below is the output of the function call:
sum = 0, currSet = [], index = 0
sum = 0, currSet = [], index = 1
sum = 0, currSet = [], index = 2
sum = 0, currSet = [], index = 3
sum = 11, currSet = [11], index = 3
sum = 5, currSet = [5], index = 2
sum = 5, currSet = [5], index = 3
sum = 16, currSet = [5, 11], index = 3
sum = 1, currSet = [1], index = 1
sum = 1, currSet = [1], index = 2
sum = 1, currSet = [1], index = 3
sum = 12, currSet = [1, 11], index = 3
sum = 6, currSet = [1, 5], index = 2
sum = 6, currSet = [1, 5], index = 3
sum = 17, currSet = [1, 5, 11], index = 3
答案1
得分: 1
以下是翻译好的内容：
你的代码部分没有问题。让我们来看一下：
class Solution{
// 生成给定集合 S 的幂集的函数
public static void determinePowerSet(int[] baseSet, List<Integer> currSet, int index, int sum)
{
// 如果当前索引在末尾，我们已经完成了子集的生成
if (index == baseSet.length) {
for(int i : currSet)
System.out.print(i+" ");
System.out.println();
return;
}
// 将当前元素添加到列表中的子集
List<Integer> addToSet = new LinkedList<Integer>(currSet);
addToSet.add(baseSet[index]);
// 不将当前元素添加到集合中
determinePowerSet(baseSet, currSet, index + 1, sum);
// 将当前元素添加到集合中
determinePowerSet(baseSet, addToSet, index + 1, sum + baseSet[index]);
}
public static void main(String[] args)
{
determinePowerSet(new int[] {1, 5, 11, 5}, new LinkedList<Integer>(), 0, 0);
}
}
***输出:***
5
11
11 5
5
5 5
5 11
5 11 5
1
1 5
1 11
1 11 5
1 5
1 5 5
1 5 11
1 5 11 5
英文:
Everything is fine in your code. Let's take a look:
class Solution{
// Function to generate power set of given set S
public static void determinePowerSet(int[] baseSet, List<Integer> currSet, int index, int sum)
{
// If the current index is at the end, we've finished generating subsets
if (index == baseSet.length) {
for(int i : currSet)
System.out.print(i+" ");
System.out.println();
return;
}
// The subset in which we add the current element in the list
List<Integer> addToSet = new LinkedList<Integer>(currSet);
addToSet.add(baseSet[index]);
// Do not add the current element to the set
determinePowerSet(baseSet, currSet, index + 1, sum);
// Add the current element to the set
determinePowerSet(baseSet, addToSet, index + 1, sum + baseSet[index]);
}
public static void main(String[] args)
{
determinePowerSet(new int[] {1, 5, 11, 5}, new LinkedList<Integer>(), 0, 0);
}
}
OUTPUT:
5
11
11 5
5
5 5
5 11
5 11 5
1
1 5
1 11
1 11 5
1 5
1 5 5
1 5 11
1 5 11 5
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论