使用字符串打印 r 元素的所有可能组合

Question

我试图用这个简单的递归和回溯来解决这个问题 approach.My 想法是这样的：

代码

import java.util.*;

public class Main
{

    static void generate(String s, String ans , int r)
    {
        if(ans.length()-1==r)
        {
            System.out.print(ans);

            return;
        }

        char ch=s.charAt(0);

        for(int i=1;i<=s.length()-1;i++)
        {
            String ros=s.substring(i);

            generate(ros,ans+ch,r);
        }
    }

    public static void main(String[] args) {
        String a="123";
        Scanner sc=new Scanner(System.in);
        int r=sc.nextInt();
        String ans=" ";
        generate(a,ans,r);
    }
}

我的字符串输出为 123 : 12

要求输出：12 13 23

我希望我的递归树是正确的，但我无法对其进行编码。我的代码似乎有一些重大问题

Answer 1

如果我理解正确，输入“12345”和3，输出应该是

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

那这就是我的程序

import java.util.*;


public class Main{
    static void generate(String s, int r){
        recursiveGenerate(s, new LinkedList<>(), r, 0);
    }

    static void recursiveGenerate(String s, Deque<Character> cache, int len, int start){
        if(cache.size() == len){
            System.out.println(Arrays.toString(cache.toArray()));
        }
        else{
            for(int i = start; i < s.length(); i++){
                cache.addLast(s.charAt(i));
                recursiveGenerate(s, cache, len, i + 1);
                cache.removeLast();
            }
        }
    }

    public static void main(String[] args){
        String a = "12345";
        int r = 3;
        generate(a, r);
    }
}

Answer 2

Here is different code using ArrayList but using same logic as **Nathan Drake** :

import java.util.*;

public class Main

{

    public static void PrintAllCombinations(int[] arr, int r) {
List<Integer> list = new ArrayList<Integer>();
PrintAllCombinationsUtils(arr, r, list, 0);
}

private static void PrintAllCombinationsUtils(int[] arr, int r, List<Integer> list, int start) {

if (list.size() >= r) {

System.out.println(list);

return;

}

for (int i = start; i < arr.length; i++) {

list.add(arr[i]);

PrintAllCombinationsUtils(arr, r, list, i + 1);

list.remove(list.size() - 1);

}

}

    public static void main(String[] args){

        Scanner sc=new Scanner(System.in);

        int r=sc.nextInt();

        int arr[]=new int[5];

        for(int i=0;i<arr.length;i++)

        {
            arr[i]=sc.nextInt();

        }

        PrintAllCombinations( arr, r);

    }
}

使用字符串打印 r 元素的所有可能组合

Print all possible combinations of r elements using string

java

string

recursion

recursive-backtracking