In tất cả dãy con (subsequence) của chuỗi trong C++

Cho chuỗi, in tất cả dãy con. Dãy con tạo bằng cách xóa ký tự, giữ nguyên thứ tự.

Input: xyz Output: x,y,z,xy,yz,xz,xyz

Nhiều phương pháp:

1. Chọn/bỏ ký tự: Đệ quy, mỗi ký tự có 2 lựa chọn: lấy hoặc bỏ.
2. Duyệt và xóa: Dùng HashSet lưu dãy con đã tìm.
3. Cố định ký tự: Cố định từng ký tự, đệ quy sinh dãy con.

Ví dụ phương pháp 1 (Java)

import java.util.*;
class Main{
    static ArrayList<String> subStringSeq = new ArrayList<>();
    public static void main(String[] args) {
        String s = "pqrs";
        System.out.println("Tất cả dãy con:");
        findSubString(s, "");
        System.out.println(subStringSeq);
    }
    static void findSubString(String s, String ans) {
        if(s.length()==0){
            subStringSeq.add(ans);
            return;
        }
        findSubString(s.substring(1), ans + s.charAt(0));
        findSubString(s.substring(1), ans);
    }
}

Kết quả

[pqrs, pqr, pqs, pq, prs, pr, ps, p, qrs, qr, qs, q, rs, r, s, ]

Phương pháp 2 (Java - HashSet)

import java.util.HashSet;
public class Main{
    static HashSet<String> subString = new HashSet<>();
    static void findSubString(String str){
        for (int i = 0; i < str.length(); i++) {
            for (int j = str.length(); j > i; j--) {
                String sub_str = str.substring(i, j);
                if (!subString.contains(sub_str)) subString.add(sub_str);
                for (int k = 1; k < sub_str.length() - 1; k++) {
                    StringBuffer sb = new StringBuffer(sub_str);
                    sb.deleteCharAt(k);
                    if (!subString.contains(sb.toString()))
                        findSubString(sb.toString());
                }
            }
        }
    }
    public static void main(String[] args){
        String s = "pqrs";
        System.out.println("Dãy con là:");
        findSubString(s);
        System.out.println(subString);
    }
}

Kết quả

[rs, pq, qr, pr, qs, ps, prs, p, pqr, q, r, s, pqs, qrs, pqrs]

Phương pháp 3 (Java - Cố định ký tự)

class Main {
    static void subString(String str, int n, int index, String curr){
        if (index == n) return;
        System.out.print(curr + ", ");
        for (int i = index + 1; i < n; i++){
            curr += str.charAt(i);
            subString(str, n, i, curr);
            curr = curr.substring(0, curr.length() - 1);
        }
    }
    static void printSubStrings(String str){
        subString(str, str.length(), -1, "");
    }
    public static void main(String[] args){
        String str = "pqrs";
        System.out.println("Các dãy con:");
        printSubStrings(str);
    }
}

Kết quả

p, pq, pqr, pqrs, pqs, pr, prs, ps, q, qr, qrs, qs, r, rs, s