Question

JAVA递归找所有子集

比如“rum”的子集有“rum”, “ru”, “rm”, “r”, “um”, “u”, “m”, “” .

这个是Tester：
import java.util.Collections;
import java.util.ArrayList;
/**
This program tests the subset generator.
*/
public class SubsetGeneratorTester
{
public static void main(String[] args)
{
SubsetGenerator generator = new SubsetGenerator("rum");

ArrayList<String> subsets = generator.getSubsets();
Collections.sort(subsets);
System.out.println(subsets);
System.out.println("Expected: [, m, r, rm, ru, rum, u, um]");
}
}

Answer 1

package web;

import java.util.ArrayList;

public class SubsetGenerator
{
	int[] indexs = null;

	int COUNT = 1;// choose how many to be combination

	ArrayList<String> list = new ArrayList<String> ();

	private String subsets;

	public SubsetGenerator( String subsets )
	{
		this.subsets = subsets;
	}

	public ArrayList<String> getSubsets ( int... params )
	{
		if(params.length == 0)
		{
			indexs = new int[subsets.length ()];
			params = new int[2];
			params[0] = 0;
			params[1] = -1;
			list.add ("");
		}
		params[1]++;
		if(params[1] > COUNT - 1)
		{
			return list;
		}
		for( indexs[params[1]] = params[0]; indexs[params[1]] < subsets.length (); indexs[params[1]]++ )
		{
			getSubsets (indexs[params[1]] + 1, params[1]);
			if(params[1] == COUNT - 1)
			{
				String temp = "";
				for( int i = COUNT - 1; i >= 0; i-- )
				{
					temp += subsets.charAt (indexs[params[1] - i]);
				}
				list.add (temp);
			}
		}
		if(COUNT < subsets.length () && params[0] == 0)
		{
			COUNT++;
			getSubsets (0, -1);
		}
		return list;
	}
}

package web;

import java.util.ArrayList;
import java.util.Collections;

public class SubsetGeneratorTester
{
	public static void main ( String[] args )
	{
		SubsetGenerator generator = new SubsetGenerator ("rum");
		ArrayList<String> subsets = generator.getSubsets ();
		Collections.sort (subsets);
		
		if(!"[, m, r, rm, ru, rum, u, um]".equals (subsets.toString ()))
		{
			System.err.println ("Expected: [, m, r, rm, ru, rum, u, um]");
		}
		else
		{
			System.err.println ("Congratulations !");
			System.out.println ("Your result is: " + subsets);
		}
	}
}

追问

public ArrayList getSubsets ( int... params ) 不能有参数的

追答

楼主，修改好了，查收

Answer 2

import java.util.ArrayList;




public class Test {
	ArrayList<String> list = new ArrayList<String>();
	String input = "input";

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Test t = new Test();
		t.p();
		System.out.println(t.list);
	}
	
	public void p() {
		for (int i=0;i<=input.length();i++) {
			for (int j=i;j<=input.length();j++) {
				if (j != i) {
					String str = input.substring(i,j);
					list.add(str);
				}
			}
		}
	}
}

追问

要用recursion啊