バックトラックで文字列を回文だけに区切る方法を全部集める

def palindrome_parts(s):
    n = len(s)
    out = []
    path = []

    def walk(i):
        if i == n:
            out.append(path[:])
            return
        for j in range(i, n):
            w = s[i:j + 1]
            if w != w[::-1]:
                continue
            path.append(w)
            walk(j + 1)
            path.pop()

    walk(0)
    return out

function palindromeParts(s) {
  const out = [];
  walk(s, 0, [], out);
  return out;
}

function walk(s, i, path, out) {
  if (i === s.length) {
    out.push([...path]);
    return;
  }
  const n = s.length;
  for (let j = i; j < n; j++) {
    if (!isPal(s, i, j)) {
      continue;
    }
    const w = s.slice(i, j + 1);
    path.push(w);
    walk(s, j + 1, path, out);
    path.pop();
  }
}

function isPal(s, i, j) {
  while (i < j) {
    if (s[i] !== s[j]) {
      return false;
    }
    i++;
    j--;
  }
  return true;
}

func palindromeParts(
	s string,
) [][]string {
	n := len(s)
	out := [][]string{}
	path := []string{}
	var walk func(i int)
	walk = func(i int) {
		if i == n {
			p := []string{}
			p = append(p, path...)
			out = append(out, p)
			return
		}
		for j := i; j < n; j++ {
			if !isPal(s, i, j) {
				continue
			}
			w := s[i : j+1]
			path = append(path, w)
			walk(j + 1)
			path = path[:len(path)-1]
		}
	}
	walk(0)
	return out
}

func isPal(
	s string, i, j int,
) bool {
	for i < j {
		if s[i] != s[j] {
			return false
		}
		i++
		j--
	}
	return true
}