組み合わせアルゴリズム——華為面接の問題

1、abc、2が入力されるとab、ac、bcが出力される
2、abcd、3を入力とabc、abd、acd、bcdが出力される
実装コードは次のとおりです.

package com.funny.algorithm;

/**
 * 1、  abc 2，  ab、ac、bc
 * 2、  abcd 3，  abc、abd、acd、bcd
 */
import java.util.Scanner;

public class Exercise1 {
	public static void main(String[] args) {
		combSelect(0, 1, "abc", 2, "");
	}

	/**
	 * 
	 * @param head
	 *                  
	 * @param length
	 *                 result  length   
	 * @param str
	 *                 
	 * @param cut
	 *                       
	 * @param result
	 *              
	 */
	private static void combSelect(int head, int length, String str, int cut, String result) {

		//  s       result 
		String s = result;
		for (int i = head; i < str.length() - (cut - length); i++) {
			//         length             cut     ，     
			if (length < cut) {
				result += str.substring(i, i + 1);
				combSelect(i + 1, length + 1, str, cut, result);
			}
			//         cut       ，      
			else if (length == cut) {
				result += str.substring(i, i + 1);
				System.out.println(result);
			}
			// result          ，  ：  ab ，     ，         ，   a      c
			result = s;

		}
	}
}

テーマ分析:
str:既存文字列      Cut:切り取った文字列の長さ     result:切り取った文字列     length:現在切り取られているのはlength文字目です
2つの条件から、これは1つの文字列の切り取りの問題であり、与えられた整数に基づいて既存の文字列(str)の中で対応する長さ(cut)の文字列を切り取り、出力された文字列の中の文字のソート順は元の文字列の中の文字の配列順、すなわちabの中のaの下に0、bの下に1、a
abc、2を例にとると、まずabcの最初の文字からresultの最初の文字を取り、最初の文字をaと取ります.では、最初の文字はどれまで取ることができますか.全部でcut(2)文字を切り取る必要があります.現在切り取っているのは第length(1)文字です.strの中で私はcut-length文字を予約しなければなりません.つまり、第1文字は最大1と下付き文字を取ります.下付き文字は0から始まるので、第1文字の下付き文字はstr.length()-(cut-length)より小さくなければなりません.現在取得されているlength番目の文字にかかわらず、strにcut-length番目の文字を残しておく必要があります.そうしないと、最後に切り取った文字の長さはcutの長さに達しません.最初の文字を取ると、最初の下に0と表示されます.そのため、次のようになります.

for(int i=0;i

1文字目を取った後、2文字目を取りに行くには、下の文字が1のところからしか検索できないはずですが、1文字目を取る原理と同じであることがわかります.2文字目がstrで切り取った文字の下の文字がstr.length()-cut+lengthを超えないことを保証すれば、lengthが2になると同時に、2文字目を取る場合、strでの開始検索の下付き文字が最初の文字であるべきときstrでの下付き文字+1、すなわち最初の文字がstrでの下付き文字が0、2番目の文字が1から検索を開始する場合、再帰ループを使用することができる:

combSelect(i+1,length+1，str,cut,result);

再帰サイクルに入った以上、終了条件が必要であることを意味し、そうでないと無限のデッドサイクルに陥るので、いつ終了するのか、lengthは現在取るべき第length文字を表し、最終長さはcutであるべきであるため、length=cutの場合、combSelectに入るのではなく、今回取るべき出力結果を表し、length

                      //         length             cut     ，     
			if (length < cut) {
				result += str.substring(i, i + 1);
				combSelect(i + 1, length + 1, str, cut, result);
			}
			//         cut       ，      
			else if (length == cut) {
				result += str.substring(i, i + 1);
				System.out.println(result);
			        }

出力後、abc、2のように、最初の文字aを取り、再帰し、2番目の文字bを取り、このときプログラムは2番目の文字のサイクルの中で、条件はi=1である.i<3-2+2;i++すなわちi<3;bを取ったとき、i=1で、2番目の文字には他の選択肢があることを説明します.bだけではありません.では、iを2にしてacに重ねます.しかし、resultはabになりました.どうやってaにしますか.そのため、ループが始まる前に、forループに入っていないときのresult値を保存する文字列を定義します.

String s = result;

これにより,ループ毎にresultをsに変更すると,再びループを重ねることができる.
問題が解決する.over-(以上はいずれも個人の粗浅な理解と解釈であり、異なる解法と観点があれば指摘を歓迎する)