Java递归求解数组里“数组合”

深碍√TFBOYSˉ_ 2022-07-16 05:42 176阅读 0赞

题目要求如下：

给定一个字符串数组，数组中的元素各不相同，把一个数组里的“数组合”全部列出，比如1和2列出来为1，2，12，21.一共有4个“数组合”

**输入描述：**

第一行输入数为数组元素个数，第二行输入数组元素

**输出描述：**

给定的数组有多少个“数组合”

**输入例子：**

3
    1 2 3

**输出例子：**

解题思路，本题可以考虑使用循环递归的算法：

以下代码仅供参考

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Scanner;
    
    
    public class Main{
            static int index=0;
    	public static void main(String[] args) {
    		Scanner mScanner=new Scanner(System.in);
    		int num=mScanner.nextInt();
    		List<String> array=new ArrayList<String>();
    		for (int i = 0; i < num; i++) {
    			array.add(mScanner.next()+"");
    		}
            listAll(array, "");
            System.out.println(index-1);
    	}
    
    	public static void listAll(List list, String prefix) {
    		index++;
    		//if (list.isEmpty()) {
    		 // System.out.print(prefix+" ");
    	    //}
    		int len = list.size();
    		for (int i = 0; i < len; i++) {
    			List temp = new LinkedList(list);
    			listAll(temp, prefix + temp.remove(i));
    		}
    	}
    }

后来我又想了下，觉得这样理解

假设输入数据为n,输出的结果为f(n).

f(n)=n\*f(n-1)+n;

在f(n-1)的基础上，当新增一个元素时，这个元素可以替代原来结果中的每个元素的位置，这样就可以有n\*f(n-1)的结果，然后当结果中长度为n时，还有n个可以满足，可以认为将新增的元素插入到原先已经排好序的结果中。这样新增一个元素后，f(n)结果就为n\*f(n-1)+n.

好吧，我表达能力有限，不知道讲清楚没。

如果对上面内容有问题，欢迎留言指出。