バックトラック法を用いた組み合わせ合計問題の解法
39. 組み合わせ合計問題（重複選択可）
整数配列candidatesと目標値targetが与えられたとき、配列要素の和がtargetとなる全てのユニークな組み合わせを返します。各要素は無制限に再利用可能です。
入力例: candidates = [2,3,6,7], target = 7
出力例: [[2,2,3],[7]]
解法ポイント:
要素の重複使用を許可するため、再帰呼び出し時にインデックスを進めない
枝刈り処 ...
8月1日 05:05 投稿
バックトラックアルゴリズムの理論と組み合わせ問題の実装
バックトラック法の基本概念
バックトラック法は探索手法の一種で、再帰処理と密接に関連しています。再帰処理を行う際には必ずバックトラックが発生するため、バックトラックは再帰の副産物と言えます。
バックトラック法の効率性
バックトラック法は本質的に全探索アルゴリズムであり、効率的とは言えません。ただし、枝刈り(pruning)を適用することで多少の効率改善 ...
7月16日 16:50 投稿