x

LQDuy:

Mình đang cố gắng giải bài này https://leetcode.com/problems/coin-change-ii/ theo backtracking.
Hiện tại mình thấy logic của mình đang chạy backtracking ổn theo mình nghĩ. Tuy nhiên, có một yếu tố yêu cầu đề bài mà nó không đáp ứng được. Cụ thể: giả sử có 5 đồng, và coin là [1,2], nó không nhận ra được các trường hợp dưới đây là như nhau: 1+1+1+2 và 1+2+1+1
Mình muốn nhờ các bạn giúp dùm cách để sửa backtracking logic để giải được bài này.
Đây là logic mà mình implement backtracking.
1) mổi node có 1 state variable là remainingAmount.
2) để đi giữa các branch trong cùng hàng/level của tree, thì mình dùng for loop, đi qua lần lượt các coin.
3) để đi xuống dưới node child thì dùng recursive call, bỏ vào index của coin cho lần tới, và số tiền còn lại.
a) mình tính trước số tiền còn lại rồi mới gọi recursive function. Do đó chỉ đi tiếp xuống level thấp hơn nếu remaining>=0.
4) back tracking được thực hiện khi recursive function trả về kết quả.
a) node con chỉ trả về kết quả = 1 khi remainingAmount=0
b) value của mỗi state là ans. Được cộng với kết quả của node con.
c) khi backtracking, mình thêm một thủ thuật để reset remainingAmount.
Thực hiện với test mẫu là [1,2,5] thì mình expect kết quả là 9, logic của mình chạy ra đúng kết quả.
Tuy nhiên, mình cần thêm logic để loại bỏ trường hợp lặp lại thì mới đúng kết quả của đề bài.
Mình muốn nhờ các bạn giúp xử lý logic này.

Bấm để mở rộng...

hungem898:

đang vào xem sex lại phải code. sort array rồi so sánh với kq cũ là đc mà

Bấm để mở rộng...

Vjpprovv:

Nhìn mặt quen vl, trước làm tiktok à?

Bấm để mở rộng...

hungem898:

Tiktok có gần 1m fl cụ thể là 10

Bấm để mở rộng...

FanBrando:

Em sofm giờ nghỉ stream LOL qua học code à

Bấm để mở rộng...