1

次の問題はコーディングバットからのものです: int の配列が与えられた場合、グループの合計が指定されたターゲットになるように、いくつかの int のグループを選択することは可能ですか?

サイトの作成者は、次のソリューションを提供しています。

public boolean groupSum(int start, int[] nums, int target) {
  if (start >= nums.length) return (target == 0);
  if (groupSum(start + 1, nums, target - nums[start])) return true;
  if (groupSum(start + 1, nums, target)) return true;
  return false;
}

nums=[2,4,8] で groupSum(0,nums,10) と呼ばれる次のケースを試したいとします。

とgroupSum(0,nums,10)が呼び出されることがわかりました。groupSum(1,nums,10)groupSum(1,nums,8)

groupSum(1,nums,10)通話groupSum(2, nums,10)とgroupSum(2, nums,6)

groupSum(1,nums,8)通話groupSum(2,nums,8)とgroupSum(1,nums,4)

等...

コードを調べてみると、次の呼び出しが表示されます。

groupSum(3,nums,10)
groupSum(3,nums,2)
groupSum(3,nums,6)
groupSum(3,nums,-2)
groupSum(3,nums,8)
groupSum(3,nums,0)
groupSum(3,nums,4)
groupSum(3,nums,-4)

最初の行のために trueをgroupSum(3,nums,0)返すはず
if (start >= nums.length) return (target == 0);ですが、 のような他の呼び出しについて混乱していますgroupSum(3,nums,-4)。最初の行から、それは明らかに false になるはずtarget != 0です。

また、return trueステートメントが必要な理由を誰かが説明できますか

if (groupSum(start + 1, nums, target - nums[start])) return true;

最初の行で真偽が決まると思っていました。

if (groupSum(start + 1, nums, target)) return true;
4

2 に答える 2

7

基本的に、関数は次のように分解できます。

  1. "start" (数値の配列内の現在の位置) が配列の末尾の一部である場合 (つまり、すべての数値を試した場合)、ターゲットに到達した場合 (つまり、ゼロ）

  2. start+1それ以外の場合は、現在の数を含めて ( )反復を続け( target-nums[start])、それが機能する場合は戻りますtrue

  3. それ以外の場合、現在の番号を含めてもうまくいかなかったので、現在の番号なしで反復を続けます。それが機能する場合は、戻りますtrue

  4. ここまで来たら、有効な数値を追加する方法がないため、 を返しfalseます。

考えられるすべての関数呼び出しのステップを分類しました。観察したように、true を返すステップ (ターゲットがゼロのステップ) があります。このtrue結果は再帰をカスケードして、最終的な戻り値になります。

これがどのように機能するかの大まかな内訳は次のとおりです。

groupSum(0,[2,4,8],10)
0 >= 3? no, so continue:
groupSum(1,[2,4,8],10-2)?
  1 >= 3? no, so continue:
  groupSum(2,[2,4,8],8-4)?
    2 >= 3? no, so continue:
    groupSum(3,[2,4,8],4-8)?
      3 >= 3? yes. -4 == 0? no, return false
    groupSum(3,[2,4,8],4)?
      3 >= 3? yes. 4 == 0? no, return false
    return false
  groupSum(2,[2,4,8],8)?
    2 >= 3? no, so continue:
    groupSum(3,[2,4,8],8-8)?
      3 >= 3? yes. 0 == 0? yes, return true
    yes, return true
  yes, return true
yes, return true

お役に立てれば！

于 2013-08-03T04:39:08.413 に答える
2

Java での Kolink の詳細なウォークスルーに加えて、私はこれを作成して、次のことを理解できるようにしました。

public class TestRecursion{

    public static boolean groupSum(int start, int[] nums, int target, String s) {
        System.out.println(new String(new char[start]).replace("\0", "    ")+"start="+start+" target="+target+" parent="+s);
        if (start >= nums.length) return (target == 0);
        if (groupSum(start + 1, nums, target - nums[start], "A:"+start+"_"+target)) return true;
        if (groupSum(start + 1, nums, target, "B:"+start+"_"+target)) return true;
        return false;
    }

    public static void main(String... args){
        int[] nums = {2,4,8};
        groupSum(0, nums, 10, "");
    }
}

出力：

start=0 target=10 parent=
    start=1 target=8 parent=A:0_10
        start=2 target=4 parent=A:1_8
            start=3 target=-4 parent=A:2_4
            start=3 target=4 parent=B:2_4
        start=2 target=8 parent=B:1_8
            start=3 target=0 parent=A:2_8
于 2013-08-03T05:05:45.717 に答える