組合せ問題（Leetcode77）

// アプローチ: 1からnまでの数を再帰的に探索し、リストでk個の組み合わせが作成されたかを記録
// 各ループの開始値が前の値と重複しないように、開始インデックスを設定
class Solution {
    private List<List<Integer>> 結果;
    private List<Integer> 現在の組み合わせ;
    private int 目標サイズ;
    
    public List<List<Integer>> combine(int n, int k) {
        結果 = new ArrayList<>();
        現在の組み合わせ = new ArrayList<>();
        目標サイズ = k;
        探索(n, k, 1);
        return 結果;
    }
    
    private void 探索(int 最大値, int 残り数, int 開始位置) {
        if(現在の組み合わせ.size() == 目標サイズ) {
            結果.add(new ArrayList<>(現在の組み合わせ));
            return;
        }
        
        for (int i = 開始位置; i <= 最大値 - (残り数 - 現在の組み合わせ.size()) + 1; i++) {
            現在の組み合わせ.add(i);
            探索(最大値, 残り数, i + 1);
            現在の組み合わせ.remove(現在の組み合わせ.size() - 1);
        }
    }
}

組み合わせ合計（Leetcode216）

// 各位置の数値を探索（startIndexで重複を防止）
// sumで現在の合計を記録。超えた場合はreturn
// k個の数値が格納されたらsumがnに等しいか判定
class Solution {
    private List<List<Integer>> 結果;
    private List<Integer> 現在の組み合わせ;
    
    public List<List<Integer>> combinationSum3(int k, int n) {
        結果 = new ArrayList<>();
        現在の組み合わせ = new ArrayList<>();
        探索(n, k, 1, 0);
        return 結果;
    }

    private void 探索(int 目標値, int 要求数, int 開始位置, int 現在和) {
        if(現在和 > 目標値) {
            return;
        }
        
        if(現在の組み合わせ.size() == 要求数) {
            if(現在和 == 目標値) {
                結果.add(new ArrayList<>(現在の組み合わせ));
            }
            return;
        }
        
        for(int i = 開始位置; i <= 9 - (要求数 - 現在の組み合わせ.size()) + 1; i++) {
            現在の組み合わせ.add(i);
            探索(目標値, 要求数, i + 1, 現在和 + i);
            現在の組み合わせ.remove(現在の組み合わせ.size() - 1);
        }
    }
}

電話番号の組み合わせ（Leetcode17）

// xは現在位置でどの集合を探索するかを記録
class Solution {
    private int[] 数字配列;
    private String[] 文字配列 = new String[10];
    private List<String> 結果;
    
    public List<String> letterCombinations(String digits) {
        // 数字と対応する文字のマッピング
        文字配列[2] = "abc";
        文字配列[3] = "def";
        文字配列[4] = "ghi";
        文字配列[5] = "jkl";
        文字配列[6] = "mno";
        文字配列[7] = "pqrs";
        文字配列[8] = "tuv";
        文字配列[9] = "wxyz";
        
        結果 = new ArrayList<>();
        数字配列 = new int[digits.length()];
        
        // 入力文字列を数値配列に変換
        for (int i = 0; i < digits.length(); i++) {
            数字配列[i] = digits.charAt(i) - '0';
        }
        
        if(digits.length() == 0) {
            return 結果;
        }
        
        StringBuilder 文字列 = new StringBuilder();
        探索(0, 文字列);
        return 結果;
    }
    
    private void 探索(int 現在位置, StringBuilder 文字列) {
        if(文字列.length() == 数字配列.length) {
            結果.add(new String(文字列));
            return;
        }
        
        for (int i = 0; i < 文字配列[数字配列[現在位置]].length(); i++) {
            文字列.append(文字配列[数字配列[現在位置]].charAt(i));
            探索(現在位置 + 1, 文字列);
            文字列.deleteCharAt(文字列.length() - 1);
        }
    }
}

重複を許す組み合わせ（Leetcode40）

// 集合の重複を判定するために、同じツリー層で同じ数値が使用されたかを確認
// 配列をソートして同じ値をまとめることで、判定を容易にする
class Solution {
    private List<Integer> 現在の組み合わせ;
    private List<List<Integer>> 結果;
    private boolean[] 使用状況;
    
    public List<List<Integer>> combinationSum2(int[] 候補, int 目標値) {
        現在の組み合わせ = new ArrayList<>();
        結果 = new ArrayList<>();
        使用状況 = new boolean[候補.length];
        Arrays.sort(候補);
        探索(候補, 目標値, 0, 0);
        return 結果;
    }
    
    private void 探索(int[] 候補, int 目標値, int 現在和, int 開始位置) {
        if(現在和 > 目標値) {
            return;
        }
        
        if(現在和 == 目標値) {
            結果.add(new ArrayList<>(現在の組み合わせ));
            return;
        }
        
        for (int i = 開始位置; i < 候補.length; i++) {
            // 同じツリー層で使用された同じ要素はスキップ
            if (i > 0 && 候補[i] == 候補[i - 1] && !使用状況[i - 1]) {
                continue;
            }
            
            if (現在和 + 候補[i] > 目標値) {
                break;
            }
            
            使用状況[i] = true;
            現在の組み合わせ.add(候補[i]);
            探索(候補, 目標値, 現在和 + 候補[i], i + 1);
            現在の組み合わせ.remove(現在の組み合わせ.size() - 1);
            使用状況[i] = false;
        }
    }
}

回文文字列の分割（Leetcode131）

// 分割点を設定し、毎回分割点から後方を分割
class Solution {
    private List<String> 現在の分割;
    private List<List<String>> 結果;
    
    public List<List<String>> partition(String s) {
        現在の分割 = new ArrayList<>();
        結果 = new ArrayList<>();
        探索(s, 0);
        return 結果;
    }
    
    private void 探索(String 文字列, int 開始位置) {
        if(開始位置 >= 文字列.length()) {
            結果.add(new ArrayList<>(現在の分割));
            return;
        }
        
        for (int i = 開始位置; i < 文字列.length(); i++) {
            if(回文チェック(文字列.substring(開始位置, i + 1))) {
                String 区切り = 文字列.substring(開始位置, i + 1);
                現在の分割.add(区切り);
            } else {
                continue;
            }
            
            探索(文字列, i + 1);
            現在の分割.remove(現在の分割.size() - 1);
        }
    }
    
    private boolean 回文チェック(String 文字列) {
        int 左 = 0;
        int 右 = 文字列.length() - 1;
        while(左 < 右) {
            if(文字列.charAt(左) != 文字列.charAt(右)) {
                return false;
            }
            左++;
            右--;
        }
        return true;
    }
}

IPアドレスの復元（Leetcode93）

// 基本的なアプローチは同じだが、判定条件が異なる
class Solution {
    private List<String> 一時リスト;
    private List<String> 結果;
    
    public List<String> restoreIpAddresses(String s) {
        一時リスト = new ArrayList<>();
        結果 = new ArrayList<>();
        探索(s, 0);
        return 結果;
    }
    
    private void 探索(String 文字列, int 開始位置) {
        if(一時リスト.size() == 3 && 文字列.length() - 開始位置 > 3) {
            return;
        }
        
        if(一時リスト.size() > 4) {
            return;
        }
        
        if(開始位置 >= 文字列.length()) {
            if(一時リスト.size() == 4) {
                StringBuilder ビルダー = new StringBuilder();
                for(int i = 0; i < 一時リスト.size() - 1; i++) {
                    ビルダー.append(一時リスト.get(i));
                    ビルダー.append(".");
                }
                ビルダー.append(一時リスト.get(一時リスト.size() - 1));
                結果.add(ビルダー.toString());
            }
            return;
        }
        
        for (int i = 開始位置; i < 文字列.length(); i++) {
            if(IPチェック(文字列.substring(開始位置, i + 1))) {
                一時リスト.add(文字列.substring(開始位置, i + 1));
            } else {
                continue;
            }
            
            探索(文字列, i + 1);
            一時リスト.remove(一時リスト.size() - 1);
        }
    }
    
    private boolean IPチェック(String 文字列) {
        if((文字列.length() > 1 && 文字列.charAt(0) == '0') || 
           Integer.parseInt(文字列) < 0 || 
           Integer.parseInt(文字列) > 255) {
            return false;
        }
        return true;
    }
}

部分集合（Leetcode78）

// 各再帰では選択するかしないかの選択肢があり、最後の位置に到達したら結果に追加
// xは現在探索中の位置を示す
class Solution {
    private List<Integer> 現在の集合;
    private List<List<Integer>> 結果;
    
    public List<List<Integer>> subsets(int[] nums) {
        現在の集合 = new ArrayList<>();
        結果 = new ArrayList<>();
        探索(nums, 0);
        return 結果;
    }
    
    private void 探索(int[] nums, int 現在位置) {
        if(現在位置 >= nums.length) {
            結果.add(new ArrayList<>(現在の集合));
            return;
        }
        
        // 選択する場合
        現在の集合.add(nums[現在位置]);
        探索(nums, 現在位置 + 1);
        現在の集合.remove(現在の集合.size() - 1);
        
        // 選択しない場合
        探索(nums, 現在位置 + 1);
    }
}

重複を含む部分集合（Leetcode90）

class Solution {
    private boolean[] 使用済み;
    private List<Integer> 現在の集合;
    private List<List<Integer>> 結果;
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        現在の集合 = new ArrayList<>();
        結果 = new ArrayList<>();
        使用済み = new boolean[nums.length];
        Arrays.sort(nums);
        探索(nums, 0);
        return 結果;
    }
    
    private void 探索(int[] nums, int 開始位置) {
        結果.add(new ArrayList(現在の集合));
        
        if (開始位置 >= nums.length) {
            return;
        }
        
        for (int i = 開始位置; i < nums.length; i++) {
            // 重複のチェック（組み合わせ2と同様）
            if(i > 0 && nums[i] == nums[i - 1] && !使用済み[i - 1]) {
                continue;
            }
            
            使用済み[i] = true;
            現在の集合.add(nums[i]);
            探索(nums, i + 1);
            現在の集合.remove(現在の集合.size() - 1);
            使用済み[i] = false;
        }
    }
}

増加部分列（Leetcode491）

// シーケンスであるため、元の順序を変更できない
// Setを使用して同じ層の要素を重複排除
class Solution {
    private List<List<Integer>> 結果;
    private List<Integer> 現在の列;
    
    public List<List<Integer>> findSubsequences(int[] nums) {
        結果 = new ArrayList<>();
        現在の列 = new ArrayList<>();
        探索(0, nums);
        return 結果;
    }
    
    private void 探索(int 開始位置, int[] nums) {
        if(現在の列.size() >= 2) {
            結果.add(new ArrayList<>(現在の列));
        }
        
        Set<Integer> 重複排除 = new HashSet<>();
        for (int i = 開始位置; i < nums.length; i++) {
            if((!現在の列.isEmpty() && 現在の列.get(現在の列.size() - 1) > nums[i]) || 
               重複排除.contains(nums[i])) {
                continue;
            }
            
            重複排除.add(nums[i]);
            現在の列.add(nums[i]);
            探索(i + 1, nums);
            現在の列.remove(現在の列.size() - 1);
        }
    }
}

旅程の再配置（Leetcode332）

class Solution {
    // グラフの構築: keyは出発地、valueは目的地をPriorityQueueで保持（自動ソート）
    private Map<String, PriorityQueue<String>> グラフ = new HashMap<>();
    // 経路を記録するリンクリスト
    private List<String> 結果 = new LinkedList<>();
    
    public List<String> findItinerary(List<List<String>> チケット) {
        // すべてのチケットを走査し、出発地と目的地をマップに格納
        for (List<String> チケット情報 : チケット) {
            String 出発地 = チケット情報.get(0);
            String 目的地 = チケット情報.get(1);
            
            if (!グラフ.containsKey(出発地)) {
                グラフ.put(出発地, new PriorityQueue<>());
            }
            グラフ.get(出発地).add(目的地);
        }
        
        深さ優先探索("JFK"); // 出発地から深さ優先探索を開始
        Collections.reverse(結果); // リンクリストを反転
        return 結果;
    }
    
    private void 深さ優先探索(String 出発地) {
        // 出発地に辺があり、まだ目的地がある場合、目的地を取り出して再帰的に探索
        while (グラフ.containsKey(出発地) && グラフ.get(出発地).size() > 0) {
            深さ優先探索(グラフ.get(出発地).poll());
        }
        // さらに探索できる子再帰がない場合、結果リストに経路を追加
        結果.add(出発地);
    }
}