ตัวอย่างโจทย์ Leet Code

ตัวอย่างโจทย์ Backtracking

Problem 78 - Subset

https://leetcode.com/problems/subsets/description/

โจทย์แบบสั้นๆ: มี array nums ที่เก็บตัวเลขไม่ซ้ำกัน จงคืน “ทุก subset” ที่เป็นไปได้ของตัวเลข nums ออกมา

สำหรับข้อนี้ สามารถการแก้ปัญหานี้ด้วยการใช้ Backtracking (เนื่องจากต้องแตะทุก case) เราจะสร้างชุดย่อยทีละชุดโดยการเพิ่มหรือไม่เพิ่มองค์ประกอบในแต่ละขั้นตอน จากนั้นเรียกใช้ function backtrack เองอีกครั้งเพื่อสร้างชุดย่อยถัดไปออกมา

class Solution {
public:
  vector<vector<int>> subsets(vector<int> &nums) {
    vector<vector<int>> result;
    vector<int> subset;
    backtrack(result, subset, nums, 0);
    return result;
  }

private:
  void backtrack(vector<vector<int>> &result, vector<int> &subset,
                 vector<int> &nums, int start) {
    // เพิ่มชุดย่อยปัจจุบันลงในผลลัพธ์
    result.push_back(subset);

    // สร้างชุดย่อยถัดไปโดยเพิ่มหรือไม่เพิ่มองค์ประกอบ
    for (int i = start; i < nums.size(); i++) {
      subset.push_back(nums[i]);
      backtrack(result, subset, nums, i + 1);
      subset.pop_back();
    }
  }
};

ในการทำงาน เราจะเริ่มต้นด้วย subset ว่างเปล่า subset และส่งมันไปยัง function backtrack พร้อมกับตำแหน่งเริ่มต้นที่ 0

ภายใน function backtrack

1. เราเพิ่ม subset ปัจจุบัน subset ลงในผลลัพธ์ result
2. จากนั้นเราวน loop ผ่านตัวที่เหลือใน Array nums โดยเริ่มจากตำแหน่ง start
   • สำหรับแต่ละตัว เราเพิ่มมันลงใน subset
   • เรียกใช้ function backtrack อีกครั้งด้วยตำแหน่งเริ่มต้นถัดไป (i + 1) เพื่อสร้าง subset ถัดไป
   • หลังจากนั้น เราลบองค์ประกอบที่เพิ่มเข้าไปออกจาก subset เพื่อเตรียมสร้างชุดย่อยถัดไป

ตัวอย่างการทำงาน เช่น

• nums = [1][2][3]
• เริ่มต้นด้วย subset ว่าง [] และเพิ่มลงในผลลัพธ์
• เพิ่ม 1 ลงใน subset [1] และเรียกใช้ backtrack กับตำแหน่งเริ่มต้น 1
  • เพิ่ม [1] ลงในผลลัพธ์
  • เพิ่ม 2 ลงใน subset [1][2] และเรียกใช้ backtrack กับตำแหน่งเริ่มต้น 2
    • เพิ่ม [1][2] ลงในผลลัพธ์
    • เพิ่ม 3 ลงใน subset [1][2][3] และเรียกใช้ backtrack กับตำแหน่งเริ่มต้น 3
      • เพิ่ม [1][2][3] ลงในผลลัพธ์
    • ลบ 3 ออกจาก subset [1][2]
  • ลบ 2 ออกจาก subset [1]
• ไม่เพิ่มอะไรลงใน subset [] และเรียกใช้ backtrack กับตำแหน่งเริ่มต้น 1
  • เพิ่ม [] ลงในผลลัพธ์
  • เพิ่ม 2 ลงใน subset [2] และเรียกใช้ backtrack กับตำแหน่งเริ่มต้น 2
    • เพิ่ม [2] ลงในผลลัพธ์
    • เพิ่ม 3 ลงใน subset [2][3] และเรียกใช้ backtrack กับตำแหน่งเริ่มต้น 3
      • เพิ่ม [2][3] ลงในผลลัพธ์
    • ลบ 3 ออกจาก subset [2]
  • ลบ 2 ออกจาก subset []
• ไม่เพิ่มอะไรลงใน subset [] และเรียกใช้ backtrack กับตำแหน่งเริ่มต้น 2
  • เพิ่ม [] ลงในผลลัพธ์
  • เพิ่ม 3 ลงใน subset [3] และเรียกใช้ backtrack กับตำแหน่งเริ่มต้น 3
    • เพิ่ม [3] ลงในผลลัพธ์
  • ลบ 3 ออกจาก subset []

ผลลัพธ์ที่ได้คือ [[],[1],[2],[1][2],[3],[1][3],[2][3],[1][2][3]] ซึ่งเป็น subset ทั้งหมดของ [1][2][3]

การแก้ปัญหานี้มีความซับซ้อนเวลาทำงานในกรณีเลวร้ายสุดอยู่ที่ O(N * 2^N) เนื่องจากเราต้องสร้าง subset ทั้งหมด 2^N ชุด และสำหรับแต่ละ subset เราต้องผ่านองค์ประกอบทั้งหมด N องค์ประกอบ ดังนั้น เวลาก็จะคำนวนออกมาได้เป็น N * 2^N ออกมานั่นเอง

Problem 46 - Permutations

https://leetcode.com/problems/permutations/description/

โจทย์แบบสั้นๆ: มี array nums ที่เก็บตัวเลขไม่ซ้ำกัน จงเรียงตัวเลขชุดนี้ “ทุกรูปแบบ” ที่เป็นไปได้ออกมา (all permutation)

สำหรับข้อนี้ เราจะสร้างการเรียงสับเปลี่ยนทีละการเรียงสับเปลี่ยน โดยการสลับตำแหน่งของตัวเลขในแต่ละขั้นตอน จากนั้นเรียกใช้ function backtrack เองอีกครั้งเพื่อสร้างการเรียงสับเปลี่ยนถัดไป

class Solution {
public:
  vector<vector<int>> permute(vector<int> &nums) {
    vector<vector<int>> result;
    vector<int> permutation;
    backtrack(result, permutation, nums);
    return result;
  }

private:
  void backtrack(vector<vector<int>> &result, vector<int> &permutation,
                 vector<int> &nums) {
    // ถ้าขนาดของ permutation เท่ากับขนาดของ Array nums
    // แสดงว่าสร้าง permutation เสร็จแล้ว
    if (permutation.size() == nums.size()) {
      result.push_back(permutation);
      return;
    }

    // สร้าง permutation ถัดไปโดยสลับตำแหน่งของตัวเลข
    for (int i = 0; i < nums.size(); i++) {
      // ข้ามตัวเลขที่ถูกใช้ไปแล้วใน permutation ปัจจุบัน
      if (find(permutation.begin(), permutation.end(), nums[i]) !=
          permutation.end()) {
        continue;
      }

      // เพิ่มตัวเลขลงใน permutation ปัจจุบัน
      permutation.push_back(nums[i]);

      // สร้าง permutation ถัดไป
      backtrack(result, permutation, nums);

      // ย้อนกลับ (backtrack) โดยลบตัวเลขออกจาก permutation ปัจจุบัน
      permutation.pop_back();
    }
  }
};

ในการทำงาน เราจะเริ่มต้นด้วยการ สร้าง permutation ว่างเปล่าขึ้นมา permutation และส่งมันไปยัง function backtrack พร้อมกับ Array nums

ภายใน function backtrack:

1. ถ้าขนาดของ permutation ปัจจุบัน permutation เท่ากับขนาดของ Array nums แสดงว่าเราสร้าง permutation เสร็จแล้ว เราจะเพิ่ม permutation นี้ลงในผลลัพธ์ result
2. มิฉะนั้น เราจะวนลูปผ่านตัวเลขทั้งหมดใน Array nums
   • ถ้าตัวเลขนั้นยังไม่ถูกใช้ใน permutation ปัจจุบัน permutation เราจะเพิ่มตัวเลขนั้นลงใน permutation
   • จากนั้นเรียกใช้ function backtrack อีกครั้งเพื่อสร้าง permutation ถัดไป
   • หลังจากนั้น เราลบตัวเลขที่เพิ่มเข้าไปออกจาก permutation permutation เพื่อเตรียมสร้าง permutation ถัดไป

ตัวอย่างการทำงาน:

• nums = [1][2][3]
• เริ่มต้นด้วย permutation ว่าง []
• เพิ่ม 1 ลงใน permutation [1] และเรียกใช้ backtrack
  • เพิ่ม 2 ลงใน permutation [1][2] และเรียกใช้ backtrack
    • เพิ่ม 3 ลงใน permutation [1][2][3] และเพิ่มลงในผลลัพธ์
    • ลบ 3 ออกจาก permutation [1][2]
  • ลบ 2 ออกจาก permutation [1]
  • เพิ่ม 3 ลงใน permutation [1][3] และเรียกใช้ backtrack
    • เพิ่ม 2 ลงใน permutation [1][3][2] และเพิ่มลงในผลลัพธ์
    • ลบ 2 ออกจาก permutation [1][3]
  • ลบ 3 ออกจาก permutation [1]
• เพิ่ม 2 ลงใน permutation [2] และเรียกใช้ backtrack
  • เพิ่ม 1 ลงใน permutation [2][1] และเรียกใช้ backtrack
    • เพิ่ม 3 ลงใน permutation [2][1][3] และเพิ่มลงในผลลัพธ์
    • ลบ 3 ออกจาก permutation [2][1]
  • ลบ 1 ออกจาก permutation [2]
  • เพิ่ม 3 ลงใน permutation [2][3] และเรียกใช้ backtrack
    • เพิ่ม 1 ลงใน permutation [2][3][1] และเพิ่มลงในผลลัพธ์
    • ลบ 1 ออกจาก permutation [2][3]
  • ลบ 3 ออกจาก permutation [2]
• เพิ่ม 3 ลงใน permutation [3] และเรียกใช้ backtrack
  • เพิ่ม 1 ลงใน permutation [3][1] และเรียกใช้ backtrack
    • เพิ่ม 2 ลงใน permutation [3][1][2] และเพิ่มลงในผลลัพธ์
    • ลบ 2 ออกจาก permutation [3][1]
  • ลบ 1 ออกจาก permutation [3]
  • เพิ่ม 2 ลงใน permutation [3][2] และเรียกใช้ backtrack
    • เพิ่ม 1 ลงใน permutation [3][2][1] และเพิ่มลงในผลลัพธ์
    • ลบ 1 ออกจาก permutation [3][2]
  • ลบ 2 ออกจาก permutation [3]

ผลลัพธ์ที่ได้คือ [[1][2][3], [1][3][2], [2][1][3], [2][3][1], [3][1][2], [3][2][1]] ซึ่งเป็น permutation ทั้งหมดของ [1][2][3]

การแก้ปัญหานี้มีความซับซ้อนเวลาทำงานในกรณีเลวร้ายสุดอยู่ที่ O(N * N!) เนื่องจากเราต้องสร้าง permutation ทั้งหมด N! permutation และสำหรับ

Problem 39 - Combination Sum

https://leetcode.com/problems/combination-sum/description/

โจทย์แบบสั้นๆ: ให้ตัวเลข array candidates มา พร้อมกับตัวเลข target จงคืน array ของ **combinations ของ candidates ที่ สามารถรวมกันได้เท่ากับ target โดย “สามารถใช้ตัวเลขใน candidate ซ้ำกี่รอบก็ได้”

การแก้ปัญหานี้ด้วย Backtracking เราจะสร้างผลรวมของตัวเลขที่เป็นไปได้ทีละผลรวม โดยการเพิ่มหรือไม่เพิ่มตัวเลขในแต่ละขั้นตอน จากนั้นเรียกใช้ function backtrack เองอีกครั้งเพื่อสร้างผลรวมถัดไป

class Solution {
public:
  vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
    vector<vector<int>> result;
    vector<int> curr;
    backtrack(candidates, target, 0, curr, result);
    return result;
  }

private:
  void backtrack(vector<int> &candidates, int target, int start,
                 vector<int> &curr, vector<vector<int>> &result) {
    if (target < 0) {
      return;
    } else if (target == 0) {
      result.push_back(curr);
    } else {
      for (int i = start; i < candidates.size(); i++) {
        curr.push_back(candidates[i]);
        backtrack(candidates, target - candidates[i], i, curr, result); // Reuse the same index i
        curr.pop_back();
      }
    }
  }
};

การทำงาน

1. function หลัก เรามี function หลัก combinationSum ที่รับ Array ของตัวเลข candidates และเป้าหมายผลรวม target เป็น input และส่งกลับ Array ของ Array ที่เป็นผลรวมทั้งหมดที่เป็นไปได้
2. function ย่อย backtrack ภายใน function หลัก เราจะเรียกใช้ function ย่อย backtrack ที่จะทำการค้นหาผลรวมทั้งหมดที่เป็นไปได้
3. ตรวจสอบเงื่อนไขการหยุด ภายใน function backtrack เราจะตรวจสอบเงื่อนไขการหยุดก่อน
   • ถ้า target เท่ากับ 0 แสดงว่าเราพบผลรวมที่ถูกต้อง เราจะเพิ่มผลรวมปัจจุบันลงในผลลัพธ์ result
   • ถ้า target น้อยกว่า 0 หรือเราวนลูปจนถึงท้าย Array แล้ว แสดงว่าไม่สามารถสร้างผลรวมได้อีก เราจะหยุดการทำงานของ function นี้
4. สร้างผลรวมถัดไป ถ้ายังไม่ถึงเงื่อนไขการหยุด เราจะวนลูปผ่านตัวเลขทั้งหมดใน Array candidates โดยเริ่มจากตำแหน่ง start
   • เพิ่มตัวเลขปัจจุบันลงในผลรวมชั่วคราว combination
   • เรียกใช้ function backtrack อีกครั้งด้วยเป้าหมายผลรวมที่เหลือ target - candidates[i] และตำแหน่งเริ่มต้นเดิม start (เนื่องจากสามารถใช้ตัวเลขซ้ำได้)
   • หลังจากนั้น เราลบตัวเลขที่เพิ่มเข้าไปออกจากผลรวมชั่วคราว combination เพื่อเตรียมสร้างผลรวมถัดไป

ตัวอย่างการทำงานสำหรับ candidates = [2][3][6][7] และ target = 7:

• เริ่มต้นด้วยผลรวมว่าง [] และเป้าหมาย 7
• เพิ่ม 2 ลงในผลรวม [2] และเรียกใช้ backtrack กับเป้าหมาย 5
  • เพิ่ม 3 ลงในผลรวม [2][3] และเรียกใช้ backtrack กับเป้าหมาย 2
    • ไม่สามารถเพิ่มตัวเลขใดลงในผลรวมได้อีก เนื่องจากทุกตัวเลขมากกว่าเป้าหมาย
  • ลบ 3 ออกจากผลรวม [2]
  • เพิ่ม 2 ลงในผลรวม [2][2] และเรียกใช้ backtrack กับเป้าหมาย 3
    • เพิ่ม 3 ลงในผลรวม [2][2][3] และเพิ่มลงในผลลัพธ์
    • ลบ 3 ออกจากผลรวม [2][2]
  • ลบ 2 ออกจากผลรวม [2]
• ไม่เพิ่มอะไรลงในผลรวม [] และเรียกใช้ backtrack กับเป้าหมาย 7
  • เพิ่ม 3 ลงในผลรวม [3] และเรียกใช้ backtrack กับเป้าหมาย 4
    • เพิ่ม 2 ลงในผลรวม [3][2] และเรียกใช้ backtrack กับเป้าหมาย 2
      • เพิ่ม 2 ลงในผลรวม [3][2][2] แต่ผลรวมเกิน 7 จึงไม่ได้เพิ่มลงในผลลัพธ์
    • ลบ 2 ออกจากผลรวม [3][2]
    • ลบ 3 ออกจากผลรวม []
  • เพิ่ม 6 ลงในผลรวม [6] และเรียกใช้ backtrack กับเป้าหมาย 1
    • ไม่สามารถเพิ่มตัวเลขใดลงในผลรวมได้อีก เนื่องจากทุกตัวเลขมากกว่าเป้าหมาย
  • เพิ่ม 7 ลงในผลรวม [7] และเรียกใช้ backtrack กับเป้าหมาย 0
    • เพิ่ม [7] ลงในผลลัพธ์

ผลลัพธ์ที่ได้คือ [[2][2][3], [7]]

ปัญหาอื่นๆสำหรับ Backtrack

https://leetcode.com/problems/sudoku-solver/description/

สรุป

Backtrack Algorithm เป็นเทคนิคการแก้ปัญหาที่ใช้วิธีการแบบ Brute Force ในการค้นหาคำตอบที่ต้องการ โดยจะลองทุกทางเลือกที่เป็นไปได้และเลือกคำตอบที่ดีที่สุด

คำว่า "ย้อนกลับ" (Backtrack) หมายถึงหากทางเลือกปัจจุบันไม่เหมาะสม ก็จะย้อนกลับไปทางเลือกก่อนหน้าและลองทางเลือกอื่นแทน ดังนั้นจึงมีการใช้เทคนิคเรียกซ้ำ (Recursion) ในการทำงาน

เมื่อใดควรพิจารณาใช้ algorithm การย้อนกลับ

Backtrack algorithm มักถูกนำมาใช้ในกรณีดังต่อไปนี้

1. ปัญหาที่มีคำตอบได้หลายคำตอบ เช่น การหาเส้นทางทั้งหมดใน graph, การจัดเรียงตัวอักษรทั้งหมด, การแก้ปริศนาเช่น N-Queens หรือ Sudoku เป็นต้น
2. ปัญหาที่สามารถแบ่งเป็นปัญหาย่อยๆ ที่คล้ายกัน เนื่องจาก Backtrack algorithm จะแก้ปัญหาโดยการสร้างคำตอบแบบค่อยเป็นค่อยไป จึงเหมาะกับปัญหาที่สามารถแบ่งเป็นปัญหาย่อยๆ ที่มีลักษณะคล้ายกัน
3. ปัญหาที่มีข้อจำกัดหรือเงื่อนไขที่คำตอบต้องสนองตอบ เช่น ในปัญหา N-Queens ต้องวางตำแหน่ง Queen ไม่ให้ Queen ตัวใดสามารถรุกได้ เป็นต้น

โดยสรุป Backtrack algorithm เหมาะสำหรับปัญหาที่ต้องการหาคำตอบทั้งหมดหรือคำตอบที่ดีที่สุด โดยมีข้อจำกัดหรือเงื่อนไขบางประการ และสามารถแบ่งปัญหาออกเป็นปัญหาย่อยๆ ที่คล้ายกันได้