再帰を使用して配列内のすべての可能な組み合わせを繰り返し処理する方法はありますか？

Question

私は再帰を学び始めました。私は練習問題を解決していたときに非常に混乱していました。例えば

、私は、ソート順[2,3,4,5,6,7,8,9]の配列を持っていると私は最後の数9までの最初の数2から始まるdジャンプのすべての可能な組み合わせを繰り返し処理したい場合。

有効ジャンプのいくつかは、（D = 3つのジャンプのため）である：

> 9

2-> 3-> 5> 9

2-> 3-> 6-

2-> 3-> 7> 9

2-> 3-> 8> 9

2-> 4-> 5-> 9

など。

このような再帰の問題にアプローチする方法を教えてください。

Answer 1

この問題は迅速に軽減されます。リストの両端を削除します。さて、残りのリストからd-1要素を選択するだけです。 mのすべての組み合わせを長さn> mのリストに見つけることは簡単に調査されます。あなたはほぼ確実にあなたの好きな言語で解決策を見つけることができます。

あなたはその洞察力を動かすことができますか？ここ

Answer 2

が可能ホップを計算するクラスの実装である：

public class HopCalculator { 

    private int[] input; 

    public HopCalculator(int[] input) { 
    this.input = input; 
    } 

入力アレイが構築時間で与えられました。これで、さまざまな長さ（ホップ数）の異なるルートを照会できます。 出力は、可能なルートを含むSetです。 各ルートは、通過する番号を含むアレイリストです。

public Set<ArrayList<Integer>> findPossibleHops(int d) { 
    Set<ArrayList<Integer>> options = new HashSet<>(); 
    ArrayList<Integer> option = new ArrayList<>(); 
    option.add(input[0]); 

    findPossibleHopsRecursive(options, option, d-1, 1, input.length-2); 
    return options; 
    } 

    private void findPossibleHopsRecursive(Set<ArrayList<Integer>> options, ArrayList<Integer> option, int d, int begin, int end) { 
    if (d==0) { 
     option.add(input[end+1]); 
     options.add(option); 
    } 
    else { 
     if (end - begin + 1 == d) { 
      option.add(input[begin]); 
      findPossibleHopsRecursive(options, option, d - 1, begin + 1, end); 
     } else { 
      ArrayList<Integer> option1 = new ArrayList<>(); 
      option1.addAll(option); 
      option1.add(input[begin]); 
      findPossibleHopsRecursive(options, option1, d - 1, begin + 1, end); 

      ArrayList<Integer> option2 = new ArrayList<>(); 
      option2.addAll(option); 
      findPossibleHopsRecursive(options, option2, d, begin + 1, end); 
     } 
    } 
    } 
}