通过回溯找到所有合计n的子集

本文介绍了通过回溯找到所有合计n的子集的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想找到所有通过回溯求和n的整数子集

I want to find all the integer subsets that sum n via backtracking

例如整数:

1 2 3 4 5 6 7

并且n = 7

我要输出

1 2 4 1 6 2 5 3 4 7

我认为我应该将要评估的整数数组中的位置作为参数传递，但是我仍然坚持编写其余的逻辑.

I think that I should pass the position in the integer array that I'm evaluating as argument, but I'm stuck writing the rest of the logic.

到目前为止，我的代码:

My code so far:

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.Set; import java.util.TreeSet; /** * * @author talleres */ public class Main { int sum (TreeSet<Integer>ts, int temp) { int sum=0; for (Integer i: ts){ sum +=i; } return sum+temp; } static HashSet<TreeSet<Integer>> alternatives = new HashSet <TreeSet<Integer>>(); static ArrayList<TreeSet<Integer>> subsets = new ArrayList <TreeSet<Integer>>(); static TreeSet<Integer> getNextSubset (){ TreeSet<Integer> alternative = new TreeSet<Integer>(); if (!alternatives.contains(alternative)){ return alternative; } else return null; // BEWARE!! } static void findSubsets (ArrayList<Integer> numbers, int amount, int index){ TreeSet <Integer> subset = new TreeSet<Integer>(); int temp = numbers.get(index); //initialize alternative if (temp<=amount) subset.add(temp); if (temp==amount) subsets.add(subset); } public static void main(String[] args) throws IOException { // TODO code application logic here BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.println("inset integers"); ArrayList<Integer> numeros = new ArrayList<Integer>(); String line=br.readLine(); while (!line.equals("")){ numeros.add (Integer.parseInt(line)); line = br.readLine(); } Collections.sort(numeros); System.out.println("insert the amount the subsets should sum"); line = br.readLine(); int amount = Integer.parseInt(line); ArrayList<Integer> accum = new ArrayList<Integer>(); findSubsets(numeros, amount, 0); } }

推荐答案

以下是一些伪代码供您使用:

Here's some pseudo code for you to work with:

Set<Set<Integer>> subsets(Set<Integer> remaining, int n) { results = new HashSet<Set<Integer>>(); if (n == 0) results.add(empty set); for each i in remaining newRemaining = remaining \ {i} for each subresult in subsets(newRemaining, n - i) results.add(subresult + {i}) return results }

也应适用于负数. (嗯，实际上会起作用.我在编写伪代码之前实现了它并进行了测试:-)

Should work for negative numbers as well. (uhm, actually will work. I implemented it and tested it before writing the pseudo code :-)